邢振宇

（威海職業(yè)學(xué)院信息工程系）

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

一、知識(shí)簡(jiǎn)介

庫(kù)拉圖斯基定理圖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è)閉合回路（見(jiàn)上圖1ABC 就是一個(gè)回路），從而S2/f（K5）的每個(gè)連通分支至少要與K5的三條邊相鄰，同時(shí)K5的每條邊只與至多2個(gè)連通分支相鄰.考慮到K5一共有條邊，這就意味著S2/（fK5）至多有[2×4÷3]=6個(gè)連通分支，這里[x]表示取整函數(shù).

同時(shí)S2/f（K5）的每個(gè)連通分支應(yīng)該是一個(gè)圓盤，于是我們就得到了一種用圓盤沿著邊粘出S2的方法，粘出來(lái)有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)成閉合回路（見(jiàn)圖2 中的A1B1A2B2A1就是一個(gè)回路），這是因?yàn)镵3，3在同一層的3個(gè)頂點(diǎn)沒(méi)有相互連接，從而S2/f（K3，3）的每個(gè)連通分支至少要與K3，3中的4條邊相鄰，同時(shí)K3，3的每條邊至多只與2個(gè)連通分支相鄰.考慮到K3，3一共有條邊，這就意味著S2/f（K3，3）至多有[9×2÷4]=4個(gè)連通分支.類似于K5的情形，此時(shí)我們粘出來(lái)有6個(gè)頂點(diǎn)，9條邊，至多4個(gè)面.因此歐拉數(shù)2=χ（S2）≤6+4-9=1，這是一個(gè)矛盾，也就是二部圖K3，3也不可能嵌入到S2.

[1]Kuratowski，Kazimierz.Surleproblèmedescourbesgauchesento pologie.Fund.Math inFrench，1930：271-283.

[2]徐俊明.圖論及其應(yīng)用[M].中國(guó)科技大學(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.