摘 要：通過引入拓?fù)渲械囊粋€(gè)不變量——?dú)W拉示性數(shù)來證明圖論中的一個(gè)重要定理。

關(guān)鍵詞：庫拉圖斯基定理;可平面圖;定理

中國分類號(hào)：O29文獻(xiàn)標(biāo)識(shí)碼：A

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

一、知識(shí)簡介

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

定義1（點(diǎn)連通）設(shè)X是一個(gè)拓?fù)淇臻g，x，y∈X，如果X中有一個(gè)連通子集同時(shí)包含x和y，我們稱點(diǎn)x和y是連通的.

定義2（連通分支）設(shè)X是一個(gè)拓?fù)淇臻g，對(duì)X中的點(diǎn)的連通關(guān)系而言的每一個(gè)等價(jià)類成為拓?fù)淇臻gX的一個(gè)連通分支.

二、定理的證明

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

■ " ■

圖1 " " " " " " 圖2

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

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

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

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

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

參考文獻(xiàn)：

[1]Kuratowski，Kazimierz.Surleproblèmedescourbesgauchesento

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

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

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

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

[5]阿姆斯特朗.基礎(chǔ)拓?fù)鋵W(xué)[M].孫以豐，譯.人民郵電出版社，2010-04-01.

作者簡介：邢振宇，碩士研究生，研究方向：計(jì)算機(jī)代數(shù)與代數(shù)幾何。