概述
圖G=（V,E）是一個二元組（V,E）使得E⊆[V]的平方，所以E的元素是V的2-元子集。為了避免符号上的混淆，我們總是默認V∩B=Ø。集合V中的元素稱為圖G的定點（或節點、點），而集合E的元素稱為邊（或線）。通常，描繪一個圖的方法是把定點畫成一個小圓圈，如果相應的頂點之間有一條邊，就用一條線連接這兩個小圓圈，如何繪制這些小圓圈和連線時無關緊要的，重要的是要正确體現哪些頂點對之間有邊，哪些頂點對之間沒有邊。
圖論本身是應用數學的一部份，因此，曆史上圖論曾經被好多位數學家各自獨立地建立過。關于圖論的文字記載最早出現在歐拉1736年的論著中，他所考慮的原始問題有很強的實際背景。
起源
衆所周知，圖論起源于一個非常經典的問題——柯尼斯堡（Konigsberg）問題。
1738年，瑞典數學家歐拉(Leornhard Euler)解決了柯尼斯堡問題。由此圖論誕生。歐拉也成為圖論的創始人。
1859年，英國數學家漢密爾頓發明了一種遊戲：用一個規則的實心十二面體，它的20個頂點标出世界著名的20個城市，要求遊戲者找一條沿着各邊通過每個頂點剛好一次的閉回路，即“繞行世界”。用圖論的語言來說，遊戲的目的是在十二面體的圖中找出一個生成圈。這個生成圈後來被稱為漢密爾頓回路。這個問題後來就叫做漢密爾頓問題。由于運籌學、計算機科學和編碼理論中的很多問題都可以化為漢密爾頓問題，從而引起廣泛的注意和研究。
猜想
在圖論的曆史中，還有一個最著名的問題－－四色猜想。這個猜想說，在一個平面或球面上的任何地圖能夠隻用四種顔色來着色，使得沒有兩個相鄰的國家有相同的顔色。每個國家必須由一個單連通域構成，而兩個國家相鄰是指它們有一段公共的邊界，而不僅僅隻有一個公共點。這一問題最早于1852年由Francis Guthrie提出，最早的文字記載則現于德摩根于同一年寫給哈密頓的信上。包括凱萊、肯普等在内的許多人都曾給出過錯誤的證明。
泰特(Tait)、希伍德(Heawood)、拉姆齊和哈德維格(Hadwiger)對此問題的研究與推廣引發了對嵌入具有不同虧格的曲面的圖的着色問題的研究。一百多年後，四色問題仍未解決。1969年，Heinrich Heesch發表了一個用計算機解決此問題的方法。1976年，阿佩爾(Appel)和哈肯(Haken)借助計算機給出了一個證明，此方法按某些性質将所有地圖分為1936類并利用計算機，運行了1200個小時，驗正了它們可以用四種顔色染色。
四色定理是第一個主要由電腦證明的理論，這一證明并不被所有的數學家接受，因為采用的方法不能由人工直接驗證。最終，人們必須對電腦編譯的正确性以及運行這一程序的硬件設備充分信任。主要是因為此證明缺乏數學應有的規範，以至于有人這樣評論“一個好的數學證明應當像一首詩——而這純粹是一本電話簿！”
雖然四色定理證明了任何地圖可以隻用四個顔色着色，但是這個結論對于現實上的應用卻相當有限。現實中的地圖常會出現飛地，即兩個不連通的區域屬于同一個國家的情況（例如美國的阿拉斯加州），而制作地圖時我們仍會要求這兩個區域被塗上同樣的顔色，在這種情況下，四個顔色将會是不夠用的。
20世紀80-90年代曾邦哲的綜合系統論（結構論）觀将“四色猜想”命題轉換等價為“互鄰面最大的多面體是四面體”。每個地圖可以導出一個圖，其中國家都是點，當相應的兩個國家相鄰時這兩個點用一條線來連接。所以四色猜想是圖論中的一個問題。它對圖的着色理論、平面圖理論、代數拓撲圖論等分支的發展起到推動作用。
（下圖是在上下對折再左右對折以後形成一個輪胎形狀，有7個區域兩兩相連，就是說在一個環面上作圖，需要7種顔色，外國數學家構造林格證明：Np=[(7+√1+48p)/2]，p=1，N1=7。
圖論的廣泛應用，促進了它自身的發展。20世紀40-60年代，拟陣理論、超圖理論、極圖理論，以及代數圖論、拓撲圖論等都有很大的發展。
拓撲學
幾何拓撲學是十九世紀形成的一門數學分支，它屬于幾何學的範疇。有關拓撲學的一些内容早在十八世紀就出現了。那時候發現一些孤立的問題，後來在拓撲學的形成中占着重要的地位。
在數學上，關于哥尼斯堡七橋問題、多面體的歐拉定理、四色問題等都是拓撲學發展史的重要問題。
哥尼斯堡（今俄羅斯加裡甯格勒）是東普魯士的首都，普萊格爾河橫貫其中。十八世紀在這條河上建有七座橋，将河中間的兩個島和河岸聯結起來。人們閑暇時經常在這上邊散步，一天有人提出：能不能每座橋都隻走一遍，最後又回到原來的位置。這個問題看起來很簡單有很有趣的問題吸引了大家，很多人在嘗試各種各樣的走法，但誰也沒有做到。看來要得到一個明确、理想的答案還不那麼容易。
1736年，有人帶着這個問題找到了當時的大數學家歐拉，歐拉經過一番思考，很快就用一種獨特的方法給出了解答。歐拉把這個問題首先簡化，他把兩座小島和河的兩岸分别看作四個點，而把七座橋看作這四個點之間的連線。那麼這個問題就簡化成，能不能用一筆就把這個圖形畫出來。經過進一步的分析，歐拉得出結論－－不可能每座橋都走一遍，最後回到原來的位置。并且給出了所有能夠一筆畫出來的圖形所應具有的條件。這是拓撲學的“先聲”。
在拓撲學的發展曆史中，還有一個著名而且重要的關于多面體的定理也和歐拉有關。這個定理内容是：如果一個凸多面體的頂點數是v、棱數是e、面數是f，那麼它們總有這樣的關系：f+v-e=2。
根據多面體的歐拉定理，可以得出這樣一個有趣的事實：隻存在五種正多面體。它們是正四面體、正六面體、正八面體、正十二面體、正二十面體。
