基本概念
平面圖：設無向圖G，若能将G畫在一個平面上，使得任何兩條邊僅在頂點處相交，則稱G是具有平面性質的圖，簡稱平面圖，否則稱G是非平面圖。
在平面圖G中，G的邊将其所在的平面劃分成的區域稱為面，有限的區域稱為有限面或内部面，無線的區域稱為無限面或外部面，包圍面的邊稱為該面的邊界，包圍每個面的所有邊組成的回路長度稱為該面的次數（橋計算兩次）。
由定義易知，
1、如果一條邊不是橋，那它必是兩個面的公共邊界
2、橋隻能是一個面的邊界
3、兩個以一條邊為公共邊界的面稱為相鄰的
就有如下的定理：平面圖G所有面的次數之和等于邊數的兩倍（類似于握手定理）。
歐拉公式
定理：設G是一個面數為 f 的（n,m）平面圖，則 n-m+f = 2.
證：用歸納法證明，對圖的邊數做歸納
(1) m=0時，由于G是一個連通圖，是以G隻包含一個孤立頂點，具有一個外部面，1-0+1=2
(2)假設m=k時歐拉公式成立，對m=k+1做歸納。若存在懸挂邊，則删去與之相連的懸挂邊之後，邊數和定點數都減少1而面數不變，是以n-m+f不變
若不存在懸挂邊，每個頂點的度數都大于1，圖中必定存在回路C，C上任一邊都一定是兩個面的公共邊界，删去此邊，這兩個面合并為一個面。頂點數不變，邊數減1，面數減1，是以n-m+f不變。
推論1：設G是一個面數為 f 的（n,m）平面圖，且有p個連通分支，則n-m+f = p+1
證：對每個連通分支使用n-m+f即可，p=1時就是歐拉公式
推論2：假設G是一個面數為 f 的（n,m）連通簡單平面圖，n≥3,每個面的次數至少是p(p≥3)，則m ≤ (n-2) * p / (p-2)。
證：由之前的定理知，f*p≤2m,帶入歐拉公式整理即可
應用：利用該定理可以證明K3，3是非平面圖
假設K3,3是平面圖，其中最短的回路長度為4，應有9≤(6-2) * 4 / (4-2) = 6，産生沖突
推論3：設G是一個面數為 f 的(n,m)連通簡單圖且n≥3,則m≤3n-6.
證：聯通簡單圖不存在重邊和自環，是以每個面的次數最少為3，帶入定理2中的公式 m≤(n-2) * 3 / 1 = 3n-6
應用：利用該定理可以證明K5是非平面圖
假設K5是平面圖，由于K5中n=5,m=10,定理有m≤3n-6，即應有10≤3*5-6，産生沖突。
推論4：任何簡單連通圖平面圖中，至少存在一個度數不超過5的頂點。
證：若所有頂點的度數都大于5，由握手定理有6n≤2m,即m≥3n,與推論3 m≤3n-6沖突
這些定理和推論隻是圖可平面性的必要條件，滿足這些條件的圖不一定是平面圖。
庫拉托夫斯基定理
庫拉托夫斯基定理給出了判斷一個圖是否是平面圖的充分必要條件
先學習一個概念——同胚
同胚：若圖G1和G2是同構的，或者通過反複的插入或删除2度頂點，它們能變成同構，則稱G1和G2是同胚的（或稱在2度頂點内同構）
定理：一個無向圖是平面圖當且僅當它不包含與K3，3或K5同胚的子圖。 （證明比較複雜，略）
例如，證明下面的不是平面圖
(1)删除一些2度頂點及相連的邊（如圖中虛線所示）
(2)發現這是一個K3,3
(3)有由理知，不是平面圖。
參考連結：
中國大學mooc 劉铎 離散數學
個性簽名：時間會解決一切