一個圖論問題的簡單證明

摘 要：通過引入拓撲中的一個不變量——歐拉示性數來證明圖論中的一個重要定理。

關鍵詞：庫拉圖斯基定理;可平面圖;定理

中國分類號：O29文獻標識碼：A

從庫拉圖斯基定理的證明以來，很多書本都引入這個定理，它也是證明一個圖是否是可平面圖的基本定理，同時也是一個平面圖著色的基礎。本文就是通過一種容易理解和簡短的證明這個有用的定理.

一、知識簡介

庫拉圖斯基定理圖G是可平面圖當且僅當G中既不含與K5同胚的子圖，也不含與K3，3同胚的子圖.

定義1（點連通）設X是一個拓撲空間，x，y∈X，如果X中有一個連通子集同時包含x和y，我們稱點x和y是連通的.

定義2（連通分支）設X是一個拓撲空間，對X中的點的連通關系而言的每一個等價類成為拓撲空間X的一個連通分支.

二、定理的證明

定理：完全圖K5和二部圖K3，3不能嵌入S2.

■ " ■

圖1 " " " " " " 圖2

證明：先證完全圖K5不能嵌入到S2.

假設存在嵌入f：K5→S2，由于K5中三條邊才能構成一個閉合回路（見上圖1ABC就是一個回路），從而S2/f（K5）的每個連通分支至少要與K5的三條邊相鄰，同時K5的每條邊只與至多2個連通分支相鄰.考慮到K5一共有C25=10條邊，這就意味著S2/f（K5）至多有[2×4÷3]=6個連通分支，這里[x]表示取整函數.

同時S2/f（K5）的每個連通分支應該是一個圓盤，于是我們就得到了一種用圓盤沿著邊粘出S2的方法，粘出來有5個頂點，10條邊，至多6個面.因此我們有歐拉數2= χ（S2）≤5+6-10=1，這是一個矛盾，也就是完全圖K5不可能嵌入到S2.

下面再證二部圖K3，3也不可能嵌入到S2.

假設存在這樣的嵌入f：K3，3→S2，由于K3，3中四條邊才能構成閉合回路（見圖2中的A1B1A2B2A1就是一個回路），這是因為K3，3在同一層的3個頂點沒有相互連接，從而S2/f（K3，3）的每個連通分支至少要與K3，3中的4條邊相鄰，同時K3，3的每條邊至多只與2個連通分支相鄰.考慮到K3，3一共有3C13=9條邊，這就意味著S2/f（K3，3）至多有[9×2÷4]=4個連通分支.類似于K5的情形，此時我們粘出來有6個頂點，9條邊，至多4個面.因此歐拉數2= χ（S2）≤6+4-9=1，這是一個矛盾，也就是二部圖K3，3也不可能嵌入到S2.

參考文獻：

[1]Kuratowski，Kazimierz.Surleproblèmedescourbesgauchesento

pologie.Fund.Math inFrench，1930：271-283.

[2]徐俊明.圖論及其應用[M].中國科技大學出版社，2010（03）.

[3]張先迪，李正良.圖論及其應用[M].高等教育出版社，2005-02-01.

[4]迪斯特爾.圖論[M].4版.于青林，等譯.北京：高等教育出版社，2013-01-01.

[5]阿姆斯特朗.基礎拓撲學[M].孫以豐，譯.人民郵電出版社，2010-04-01.

作者簡介：邢振宇，碩士研究生，研究方向：計算機代數與代數幾何。