動機
同一個圖有許多畫法。一張圖上的交叉可能僅是畫法造成的,而非圖本身的性質。平面性問的是:能否找到一種畫法,使邊只在共同端點相交?面數恆等式把這種幾何存在性問題轉化為頂點數與邊數的算術限制。這裏討論有限簡單無向圖,並區分抽象圖與它的某個嵌入。
定義
定義 3.1.1
(平面嵌入、平面圖與面)
平面嵌入把每條邊畫成連接兩端點的簡單弧,不同邊僅能在共同端點相交,頂點也不能落在邊的內部。若圖存在平面嵌入,稱之為平面圖。從平面中去掉圖形後得到的連通區域稱為面,包括無界的外面。
一個圖可以有不同的嵌入和畫法;選作外面的區域不是抽象圖的固有頂點或邊。
對不連通畫法,把一個面的邊界長度定義為所有邊界分量上關聯邊側的總數;若橋的兩側都屬於該面,就計兩次。孤立頂點不貢獻邊側。
定義 3.1.2
(合法著色與色數)
頂點的合法著色為每個頂點分配顏色,使相鄰頂點顏色不同。色數 是合法著色所需顏色數的最小值。
孤立頂點不會對其他頂點施加限制。平面嵌入是否存在,與某個著色用了多少顏色,是不同的問題;但平面性可以幫助推出著色上界。
定理/命題
定理 3.1.3
(連通平面圖的歐拉(Euler)公式)
有限連通平面圖有 個頂點、 條邊和 個面時,。
定理 3.1.4
(簡單平面圖的邊數界)
有限簡單連通平面圖若有 個頂點,則 。
概念視角組合
有界面的個數就是生成樹以外的邊數
把公式改寫為 。連通圖的生成樹有 條邊,所以右邊數的是樹以外的邊,也就是這棵樹決定的基本圈個數。下面的證明逐步實現這個計數:每次刪去的圈邊都在最後剩下的生成樹以外,而每次刪除都減少一個有界面。因此在同一個圖的每個平面嵌入中,有界面的個數都相同,儘管它們的形狀可以不同。
證明思路
證明
(刪除圈邊直至剩下生成樹)
我們使用若爾當(Jordan)曲線定理:平面中的簡單閉曲線把平面分為內部和外部,該曲線是兩者的共同邊界。先設連通圖是樹。它有 ,其平面畫法只有一個面:從單頂點開始,每次添加葉邊不會圍出區域,因為新邊不形成閉曲線。因此 。
若圖不是樹,取圈上一條邊刪除。其餘圈邊提供替代路徑,所以刪除後仍連通。畫在平面上的該邊分隔兩個不同面:它與圈的其餘部分形成簡單閉曲線,故邊的兩側局部屬於補集的不同分支。刪除該邊恰好合併這兩個面,因此 都減少一, 不變。重複操作直到留下生成樹;邊數有限,過程終止,樹的情形便證明恆等式。
證明透視
平面在證明中的位置
計數部分很簡單;拓撲只出現在兩處。樹的情形用到:添加一條葉邊不會圍出區域,因為只在一個端點與原圖相交的新弧不在任何閉曲線上。歸納步驟恰好使用一次若爾當曲線定理:圈上的一條邊與該圈其餘部分構成簡單閉曲線,所以它的兩側屬於不同的面,刪除它恰好使 減少一。選取圈上的邊正是兩方面都成立的原因:它保持圖連通,又保證兩側是不同的面;若刪除的是橋, 不變而圖會不連通。有限性使刪除過程停止,而連通性這一假設保證終點是一棵滿足 的生成樹。
證明
(計算邊側)
為證明邊數界,計算面與邊側的關聯。每條邊有兩側,對面邊界長度之和貢獻二;即使橋的兩側屬於同一個面也要算兩次。至少有三個頂點的簡單連通平面圖,每個面的邊界長度至少為三:長度一需要自環,長度二要麼需要重邊,要麼將只有兩個頂點的連通分支中唯一一條邊走兩次。因此 。代入 ,得 ,即 。
反例模式
簡單性與三個頂點都不可省略
聲稱:每個 的連通平面圖,不論是否簡單,都滿足 。畫一個三角形,並在每條邊旁、三角形外側再畫一條平行弧。這個連通平面多重圖有 、,歐拉公式給出 :內部三角形面、外面,以及平行弧之間三個長度為二的面。但 。長度為二的面正是簡單性所排除的。頂點數條件也需要:單條邊有 ,而 時 。兩種情形中歐拉恆等式本身仍然成立;失效的只是面長度的界。
例題詳解
例題 3.1.5
(五頂點完全圖)
完全圖 的每對頂點之間有邊,故 。五頂點簡單連通平面圖至多有 條邊。矛盾證明 非平面,無須檢查所有畫法。
例題 3.1.6
(帶對角線的正方形)
正方形加一條對角線有 。將對角線畫在正方形內部,得到兩個有界三角面和一個無界面,所以 ,而 。邊數界給出 ,與畫法一致。但不等式本身不能構造嵌入,畫法才提供存在性。
例題 3.1.7
(畫在平面上的樹)
四頂點路徑有三條邊、一個面,因此 。按邊側重數計算,該面的邊界長度為六:三條橋的兩側各出現一次。若錯誤地假設每條邊屬於兩個不同面,計數就會出錯。
常見錯誤
反例模式
必要邊數界不能判定平面性
是平面性的必要條件,不是充分條件。 有 ,滿足 ,卻不是平面圖,下文將用更強的界證明。反過來,一張畫法有交叉也不意味著圖非平面:正方形兩條對角線交叉的畫法表示 ,而把一個頂點放在三角形內可以畫出無交叉的嵌入。
常見錯誤
(歐拉公式需要計入分支數)
兩個分離的三角形有 ,而不是 。若對不連通的畫法套用 ,會預言只有 個面,漏掉一個三角形內部。正確的常數是 ,見不連通畫法一節的證明。
常見錯誤
(橋的兩側屬於同一個面)
四頂點路徑唯一的面邊界長度是六而不是三:三條邊的兩側都會遇到。若每條橋只計一次,面長度之和便是 ,與面長度之和等於 這一恆等式矛盾,而本節所有邊數界都依賴這個恆等式。
總結
歐拉恆等式針對固定的平面嵌入;邊數界是抽象平面圖的推論。違反必要界可以證明非平面,通過必要界不能證明平面性。存在橋時,計算面邊界要按邊側重數計數。
練習
快速檢查
(連通平面圖有 個頂點和 條邊,有多少個面?)
解答 · 答案
歐拉公式給出 ,其中包括外面。
快速檢查
(七頂點簡單連通平面圖能否有 條邊?)
解答 · 答案
不能,因為邊數界要求 。
二部圖的更強邊數界
定義 3.1.8
(二部圖)
若頂點可以分成兩組且每條邊都連接不同組,稱圖為二部圖。
定理 3.1.9
(二分平面圖的邊數界)
對至少有三個頂點的有限簡單連通二分平面圖,。
證明
(長度至少為四的面)
每走一條邊就換組,所以任何閉遊走長度為偶數。至少有三個頂點的簡單連通二分平面圖,每個面邊界長度至少為四:前面的論證排除長度一和二,二分性排除奇數長度。即使邊界遊走重複經過橋,這個結論也成立。
計算邊側得 ,代入 ,得到
的兩組各有三個頂點,每一對跨組頂點之間有邊,所以 ,但上界要求 。因此 非平面。普通的 界沒有檢測出它;二分性的額外假設改進了結論。
起作用的是面長度條件,而不是二部圖這個名稱本身。若簡單連通平面圖每個面邊界長度至少為 ,則 ,結合歐拉公式可得
邊界長度必須包含橋的重複邊側。不能未經檢查就把某個圍長代入:樹沒有圈,卻仍然有面邊界遊走。
快速檢查
(八頂點簡單連通二分平面圖能有 條邊嗎?)
解答 · 答案
不能,二部圖界給出 。這是對所有平面畫法的不可能性證明,不只是否定某次嘗試。
按順序著色
一個簡單的著色上界不需要平面性。設有限非空圖的最大度數為 。任意排列頂點,依次從 種顏色中選色。輪到一個頂點時,至多有 個鄰點已經著色,因此至多 種顏色被禁止,至少還剩一種。於是 。
完全圖 表明這個上界可以達到:每對頂點相鄰,不能共享顏色。對具體圖,不同順序可能產生不同的顏色數,但同一上界仍然有效。因此貪心著色是「這些顏色足夠」的證書,通常不是顏色數最小的證明。
例。 四頂點路徑最大度為二,通用界給出至多三種顏色。沿路徑交替使用兩種顏色得到合法著色;因為存在邊,一種顏色不夠。因此其色數為二,最大度界在此不緊。
四色定理給平面圖更強的普遍上界,但這裏不提供證明,也不能僅用最大度界推得。有限非空簡單平面圖有度數至多五的頂點。若 ,每個頂點的度數至多為一。若 ,使用下文證明的不連通情形推廣 :度數和 ,不可能每個頂點的度數都至少為六。但只靠這個平均值步驟不能證明四色定理,還需要額外思想。
快速檢查
(證明至少有一條邊的非空森林可以用兩色著色,且色數恰為二。)
解答 · 答案
每棵樹選一個根,按頂點到根距離的奇偶著色。每條邊連接相鄰層:若一條邊連接相同奇偶的層,利用通向根的唯一路徑和該邊會形成圈。因此相鄰頂點異色。孤立頂點可取任一色。至少有一條邊,其端點必須異色,所以一種顏色不夠。
快速檢查
(平面畫法有 ,且每個面邊界長度為四。它有多少個面?)
解答 · 答案
不存在這樣的畫法。每條邊有兩側,所以各面邊界長度之和為 。若每個面的長度都是四,這個和就是 ,而 沒有整數解。這個論證既不用歐拉公式,也不用連通性。若仍套用連通形式的公式,會得到 個面,但其邊界長度之和將為 。
不連通的畫法
連通性是上述歐拉公式形式的重要條件。
定理 3.1.10
(含 個分支的歐拉公式)
對有 個連通分支的平面圖,
證明
(用橋連接各分支)
可以在平面上添加 條邊連接不同分支而不引入交叉。每條新邊都是橋,所以不會產生新面。所得連通平面圖有相同的頂點數和面數,邊數為 ;應用連通歐拉公式並整理即得結果。連接弧可畫在各面內部;若一個分支位於另一分支的圈內,先通過包含它的面把它連到該面的邊界。重複直到所有分支連通。
例如兩個分離的三角形有 :一個外面及每個三角形內部各一個面。因此 ,右邊不能誤寫為二。孤立頂點也是一個分支,但不產生新面;添加它時 同時增加一,公式仍一致。
使用邊數界時,應先處理小圖或不連通圖,不能盲目套用針對連通圖的推導。對於 的簡單平面圖, 確實也適用於不連通的情形:可在同一頂點集上添加不交叉的邊,將各分支連成簡單連通平面圖。連接兩個不同分支的邊不會與已有的邊平行,所以擴大後的圖仍是簡單圖;對它應用連通情形的界,得 。上面的面計數假設連通,不連通情形正是靠這個加邊步驟來證明。