圖論研究各種圖的性質。圖可以用來模擬現實世界中的許多情況，例如

社交網路的使用者及其友誼關係；
一個國家中的城市以及連線它們的街道；
電信網路，如網際網路和全球資訊網；
語言結構，例如句子的句法結構；
專案管理，用於管理任務之間的依賴關係；
生物資訊學：蛋白質-蛋白質相互作用、殘基相互作用網路、基因調控；
數學關係，例如使用樹的斐波那契展開；
決策樹和貝葉斯網路；
電子電路：基爾霍夫定律與電路的圖結構密切相關；
以及許多其他情況。

哥尼斯堡七橋問題

最著名也是最古老的現實世界問題是關於哥尼斯堡七橋問題。普魯士的哥尼斯堡市（現為俄羅斯的加里寧格勒）位於普列戈爾河的兩岸，包括兩個大島，它們透過七座橋相互連線並與大陸連線。

問題是找到一條穿過城市的路線，可以一次且僅一次地穿過每座橋。島嶼不能透過除橋樑以外的任何路線到達，並且每座橋都必須在每次透過時完全穿過；一個人不能走到橋上的一半，然後轉身，然後從另一邊穿過另一半。路線不必從同一個地方開始和結束。尤拉證明這個問題沒有解決方案。不可能存在一條不重複的連續曲線穿過所有七座橋。困難在於開發一種分析技術和後續測試，以用數學的嚴謹性來確定這一斷言。

首先，尤拉指出，在每個陸地上的路線選擇無關緊要。路線的唯一重要特徵是穿過的橋樑序列。這使他能夠用抽象的術語重新表述問題（為圖論奠定基礎），消除了除陸地列表和連線它們的橋樑以外的所有特徵。用現代術語來說，用抽象的“頂點”或節點替換每個陸地，用抽象的連線“邊”替換每座橋，它僅用於記錄哪對頂點（陸地）透過該橋連線。由此產生的數學結構稱為圖。

→ →

由於只有連線資訊是相關的，圖的圖形表示的形狀可以以任何方式扭曲，而不會改變圖本身。每對節點之間是否存在（或不存在）邊是重要的。例如，繪製的邊是直線還是曲線，或者一個節點位於另一個節點的左側還是右側並不重要。

接下來，尤拉觀察到（除路線的端點外），無論何時從橋進入頂點，都會從橋離開頂點。換句話說，在圖中的任何路線中，進入非終端頂點的次數等於離開它的次數。現在，如果每座橋都只被穿過一次，則對於每個陸地（可能除了選擇的起點和終點以外），接觸該陸地的橋樑數量必須是偶數（在特定的遍歷中，它們的一半將被“朝向”陸地遍歷；另一半，則被“遠離”它遍歷）。然而，原始問題中的所有四個陸地都被奇數座橋接觸（一個被 5 座橋接觸，另外三個中的每一個被 3 座橋接觸）。由於最多隻有兩個陸地可以作為假設路線的端點，因此遍歷每座橋一次的命題會導致矛盾。

用現代語言來說，尤拉證明了穿過圖的路線（只遍歷每條邊一次）的可能性取決於節點的度數。節點的度數是接觸它的邊的數量。尤拉的論點表明，所需形式路線的必要條件是圖是連通的，並且只有一個或兩個奇數度節點。這個條件也證明是充分的——這是一個由尤拉提出並後來由卡爾·希爾霍爾策證明的結果。這種路線現在被稱為尤拉路徑（oy•lɛr•i•ən）或尤拉路線，以紀念他。此外，如果有奇數度節點，則任何尤拉路徑都將從其中一個節點開始，並在另一個節點結束。由於與歷史上的哥尼斯堡相對應的圖有四個奇數度節點，因此它不可能有尤拉路徑。

問題的另一種形式要求一條遍歷所有橋樑並且起點和終點相同的路徑。這種路線稱為歐拉回路或尤拉環遊。這種迴路存在當且僅當圖是連通的，並且根本沒有奇數度節點。所有歐拉回路也是尤拉路徑，但並非所有尤拉路徑都是歐拉回路。