圖論 （英語：Graph theory ），是組合數學 分支，和其他數學分支如群論 、矩陣論、拓撲學 有着密切關係。
一個由6個頂點和7條邊組成的圖 圖 是圖論的主要研究對象。圖是由若干給定的頂點 及連接兩頂點的邊所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關係。頂點用於代表事物，連接兩頂點的邊則用於表示兩個事物間具有這種關係。
圖論起源於著名的柯尼斯堡七橋問題 。該問題於1736年被歐拉 解決，因此普遍認為歐拉 是圖論的創始人。[ 1]
圖論的研究對象相當於一維的單純複形 [ 2]
柯尼斯堡七橋問題 一般認為，歐拉 於1736年出版的關於柯尼斯堡七橋問題 的論文是圖論領域的第一篇文章[ 3] 一筆畫問題 。而此論文與范德蒙 的一篇關於騎士週遊問題 的文章，則是繼承了萊布尼茨 提出的「位置分析」的方法。歐拉提出的關於凸多邊形頂點數、棱數及面數之間的關係的歐拉公式 與圖論有密切聯繫，此後又被柯西 等人[ 4] [ 5] 拓撲學 的起源。1857年，哈密頓 發明了「環遊世界遊戲 哈密頓路徑問題 」。
西爾維斯特 於1878年發表在《自然 》上的一篇論文中首次提出「圖」這一名詞[ 6]
歐拉的論文發表後一個多世紀，凱萊 研究了在微分學 中出現的一種數學分析的特殊形式，而這最終將他引向對一種特殊的被稱為「樹 」的圖的研究。由於有機化學中有許多樹狀結構的分子，這些研究對於理論化學有着重要意義，尤其是其中關於具有某一特定性質的圖的計數 問題。除凱萊的成果外，波利亞 也於1935至1937年發表了一些成果，1959年，De Bruijn
四色問題 可謂是圖論研究史上最著名也是產生成果最多的問題之一：「是否任何一幅畫在平面上的地圖都可以用四種顏色染色，使得任意兩個相鄰的區域不同色？」這一問題由法蘭西斯·古德里 於1852年提出，而最早的文字記載則出現在德摩根 於1852年寫給哈密頓的一封信上。包括凱萊 、肯普 泰特 希伍德 、拉姆齊 和Hadwige 虧格 的曲面的圖的着色問題的研究。一百多年後，四色問題仍未解決。1969年，Heinrich Heesch 凱尼斯·阿佩爾 和沃夫岡·哈肯 藉助計算機給出了一個證明，此方法按某些性質將所有地圖分為1936類並利用計算機一一驗證了它們可以用四種顏色染色。但此方法由於過於複雜，在當時未被廣泛接受。
1860年之1930年間，若當 、庫拉托夫斯基 和惠特尼 從之前獨立於圖論發展的拓撲學中吸取大量內容進入圖論，而現代代數方法的使用更讓圖論與拓撲走上共同發展的道路。其中應用代數較早者如物理學家基爾霍夫 於1845年發表的基爾霍夫電路定律 。
圖論中概率方法的引入，尤其是埃爾德什 和Alfréd Rényi 隨機圖論 。
圖論中有許多定義，以下是一些與之相關最基本的定義。
有三個邊和三個頂點的圖。 圖論中，圖 是有序對
G
=
(
V
,
E
)
{\displaystyle G=(V,E)}
V
{\displaystyle V}
E
⊆
{
{
x
,
y
}
:
(
x
,
y
)
∈
V
2
,
x
≠
y
}
{\displaystyle E\subseteq \left\{\left\{x,y\right\}:(x,y)\in V^{2},x\neq y\right\}}
{
x
,
y
}
{\displaystyle \left\{x,y\right\}}
x
,
y
{\displaystyle x,y}
為了避免歧異，上述的定義被更精準地稱作無向簡單圖。
事實上可以推廣為更一般的定義：圖 是有序三元組
G
=
(
V
,
E
,
ϕ
)
{\displaystyle G=(V,E,\phi )}
V
{\displaystyle V}
E
{\displaystyle E}
E
{\displaystyle E}
ϕ
:
E
→
{
{
x
,
y
}
:
(
x
,
y
)
∈
V
2
}
{\displaystyle \phi :E\to \left\{\left\{x,y\right\}:(x,y)\in V^{2}\right\}}
為了避免歧異，上述的定義被更精準地稱作無向圖。
V
,
E
{\displaystyle V,E}
V
{\displaystyle V}
E
{\displaystyle E}
|
V
|
{\displaystyle |V|}
|
E
|
{\displaystyle |E|}
子圖同構問題 ：給定兩個圖
G
{\displaystyle G}
H
{\displaystyle H}
G
{\displaystyle G}
H
{\displaystyle H}
同構 。這是一個NP完全問題 。
哈密頓迴路問題 可視為一個子圖同構問題，即給定一個
n
{\displaystyle n}
n
{\displaystyle n}
一類相關的常見問題要求在給定圖中尋找符合某些條件的最大子圖，其中有很多是NP完全的，如：
類似地，有些問題要求尋找符合某些條件的最大導出子圖，如：
最大獨立集問題 ：在給定圖中尋找最大的無邊的導出子圖，亦即獨立集 （NP完全）。平面圖 判定：判定給定的圖是否是平面圖（此問題與子圖的關係，參見庫拉托夫斯基定理 ）
一個尚未解決的與子圖相關的猜想，重構猜想 （Reconstruction conjecture ）：一個n 階圖是否能夠由其所有n-1 階導出子圖唯一確定？
點色數 （Chromatic number ）邊色數 （Chromatic index ）色多項式 許多問題與將圖以特定方式染色 有關，如：
四色問題 完美圖問題 （strong perfect graph theorem ）列表染色問題，列表邊染色問題
曲面染色
卜月華; 吳建專; 顧國華; 殷翔, 《图论及其应用》 第一版, 東南大學出版社: 1-2, 2007
Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986
Cauchy, A. L., Recherche sur les polyèdres - premier mémoire, Journal de l'École polytechnique, 1813,, 9 (Cahier 16): 66–86.
L'Huillier, S.-A.-J., Mémoire sur la polyèdrométrie, Annales de Mathématiques, 1812–1813, 3 : 169–189.
Berge, Claude , Théorie des graphes et ses applications, Collection Universitaire de Mathématiques II , Paris: Dunod, 1958Biggs, N.; Lloyd, E.; Wilson, R., Graph Theory, 1736–1936, Oxford University Press, 1986 .Bondy, J.A.; Murty, U.S.R., Graph Theory, Springer, 2008, ISBN 978-1-84628-969-9 .Bondy, Riordan, O.M, Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" (S. Bornholdt and H.G. Schuster (eds)), Wiley VCH, Weinheim, 1st ed., 2003 .Chartrand, Gary , Introductory Graph Theory, Dover, 1985, ISBN 0-486-24775-9Gibbons, Alan, Algorithmic Graph Theory, Cambridge University Press , 1985 .Reuven Cohen, Shlomo Havlin, Complex Networks: Structure, Robustness and Function, Cambridge University Press, 2010 Golumbic, Martin , Algorithmic Graph Theory and Perfect Graphs, Academic Press , 1980Harary, Frank , Graph Theory, Reading, MA: Addison-Wesley, 1969Harary, Frank ; Palmer, Edgar M., Graphical Enumeration, New York, NY: Academic Press, 1973Mahadev, N.V.R.; Peled, Uri N., Threshold Graphs and Related Topics, North-Holland , 1995 .Mark Newman, Networks: An Introduction, Oxford University Press, 2010 . 
