一、基本概念

平面圖：設無向圖G，若能將G畫在一個平面上，使得任何兩條邊僅在頂點處相交，則稱G是具有平面性質的圖，簡稱平面圖，否則稱G是非平面圖。

在平面圖G中，G的邊將其所在的平面劃分成的區(qū)域稱為面，有限的區(qū)域稱為有限面或內部面，無線的區(qū)域稱為無限面或外部面，包圍面的邊稱為該面的邊界，包圍每個面的所有邊組成的回路長度稱為該面的次數(shù)（橋計算兩次）。

由定義易知，

1. 如果一條邊不是橋，那它必是兩個面的公共邊界

2. 橋只能是一個面的邊界

3. 兩個以一條邊為公共邊界的面稱為相鄰的

就有如下的定理：平面圖G所有面的次數(shù)之和等于邊數(shù)的兩倍（類似于握手定理）。

二、歐拉公式

定理：設G是一個面數(shù)為 f 的（n,m）平面圖，則 n-m+f=2.

證：用歸納法證明，對圖的邊數(shù)做歸納

(1) m=0時，由于G是一個連通圖，因此G只包含一個孤立頂點，具有一個外部面，1-0+1=2

(2)假設m=k時歐拉公式成立，對m=k+1做歸納。若存在懸掛邊，則刪去與之相連的懸掛邊之后，邊數(shù)和定點數(shù)都減少1而面數(shù)不變，因此n-m+f不變

若不存在懸掛邊，每個頂點的度數(shù)都大于1，圖中必定存在回路C，C上任一邊都一定是兩個面的公共邊界，刪去此邊，這兩個面合并為一個面。頂點數(shù)不變，邊數(shù)減1，面數(shù)減1，因此n-m+f不變。

推論1：設G是一個面數(shù)為 f 的（n,m）平面圖，且有p個連通分支，則n-m+f = p+1

證：對每個連通分支使用n-m+f即可，p=1時就是歐拉公式

推論2：假設G是一個面數(shù)為 f 的（n,m）連通簡單平面圖，n≥3,每個面的次數(shù)至少是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是一個面數(shù)為 f 的(n,m)連通簡單圖且n≥3,則m≤3n-6.

證：聯(lián)通簡單圖不存在重邊和自環(huán)，所以每個面的次數(shù)最少為3，帶入定理2中的公式 m≤(n-2) * 3 / 1 = 3n-6

應用：利用該定理可以證明K5是非平面圖

假設K5是平面圖，由于K5中n=5,m=10,定理有m≤3n-6，即應有10≤3*5-6，產生矛盾。

推論4：任何簡單連通圖平面圖中，至少存在一個度數(shù)不超過5的頂點。

證：若所有頂點的度數(shù)都大于5，由握手定理有6n≤2m,即m≥3n,與推論3 m≤3n-6矛盾

這些定理和推論只是圖可平面性的必要條件，滿足這些條件的圖不一定是平面圖。

三、庫拉托夫斯基定理

庫拉托夫斯基定理給出了判斷一個圖是否是平面圖的充分必要條件

先學習一個概念——同胚

同胚：若圖G1和G2是同構的，或者通過反復的插入或刪除2度頂點，它們能變成同構，則稱G1和G2是同胚的（或稱在2度頂點內同構）

定理：一個無向圖是平面圖當且僅當它不包含與K3，3或K5同胚的子圖。

例如，證明下面的不是平面圖

(1)刪除一些2度頂點及相連的邊（如圖中虛線所示）

(2)發(fā)現(xiàn)這是一個K3,3

(3)有由理知，不是平面圖。