一個圖論問題的簡單證明

邢振宇

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

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

一、知識簡介

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

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

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

二、定理的證明

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

圖1

圖2

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

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

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

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

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

[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.