無結圖及其若干性質論文
從1840年由數學家茂比烏斯（M6bius）提出四色猜想以來，世界各國很多專家、學者為了 證明猜想為真，做了大量工作，作出了很多卓越貢獻。但至今尚未見過猜想的理論性證明？因而 本文將從理論上作些初步探索和研究，在文獻[4]的基礎上深入討論平面圖的著色與它的拓樸 結構相互關係。建立了結、無結圖、有結圖、準色交錯路徑等概念，給出了無結圖的充分必要條 * 件以及它的一些性質。這些概念和性質對於從理論上證明四色定理將會起一定的推動作用？
1基本概念
設平面圖G可4—著色，G中分別著a，a，b，c，d色。
定義1兩色子圖[4]？在圖G中，分別著色的點以及它們之間的邊所構成的`子圖稱為 G的d兩色子圖，記為Gab。顯然，G有六種兩色子圖，它們分別為
兩色子圖（^，^/二^冶&山^^^彡的連通子圖數目記為？KXG^）。
定義2兩色交錯路徑。G中任一兩色子圖可能是連通的，也可能是分離的？若G中任 意兩點V，和Vj在兩色子圖01，（：？：，>；=^，6<，山：1：尹3^）的同一連通子圖中，則w，和v，間至少存 在一條工，3/兩色交錯路徑，用表示？
。定義3不相千點對圖G中和％著為同色，或透過Kempe法⑴交換可著為同色，稱Vi和V，為不相干點對，記為（奶；TO）。
定義4相干點對圖G中w，_和％著為異色，透過Kempe法交換也不能著為同色，稱 Vi和V，為相干點對，記為（認？ V）。若圖G的，巧，w3，w4，w5}中除和02；%）為 不相干點對外，其餘各點對均為相干點對，則稱它為仏。將圖Go嵌入一個平面，使 V4，^5均處在外區周界上，P4。5M兩色交錯路徑把非外區分為忒和A兩部分，設，Gd（t；3）C：A2。同樣，屍3。5W兩色交錯路徑把非外區分為私和B2兩部分，又設 Gac （v2）（=瓦，Gac （t；4） CZB2 ？
定義S結。若圖G。的兩色子圖山x=^y）中不含有，的，％}中任 一點，則稱J巧為G。的結。允許在一個結中只含有一個點。Go中可有六種結= —Gdbi） — Gab（v^） ； Jac — Gac ~ Gac （v2 ） — Gac （，V 4。 ） ； J ad = Gad ~~ Gad （Vl ^V2 J VS） 9 J bc^ Gbc ~ （v^ ^ V 4） ； J bd ~ Gbd —Gtdiv3 ，v5） —，Jcd = Gcd一Gcd（^4，w5）。
定義6無結圖和有結圖。若圖G。中不存在任一結人，=：關30，則稱G。為無結圖。否則，G。稱為有結圖。
定義7準色交錯路徑設圖G。中隊和巧之間不存在兩色交 錯路徑，但存在帶有第三色的路徑，且透過<^（奶）（1，3/ = ^，6<，山：1：關3^ = 1，2，3，4，5，々六 夫_；？）中色交換它可以變成R和％之間的兩色交錯路徑，那末這種三色路徑被稱為準色交錯路 徑。在G中可有四種準色交錯路徑，為了書寫方便，將它們寫成如下形式
Pl =P2，iiacbc，b^Gat{vi） ，fi^Go4（wi））
P1為W和％之間的準色交錯路徑。其中，所有6色點均屬於Ca？（W|），所有《色點均不屬於 Go4Cvi）。
P3 = PlA{acbc，a G Gab（v3），b $ Gal。（v3））
P2 = puAabcb，c 6 G？c{v2） ，a $ G沉（t；2））
P* = Pu3（abcbta G Gae{vt） ，c $ G沉（w4））
關於P3’P2和i34的涵義可以仿照屍1給予解釋，這裡不再贅述。
2定理與證明
定理 1 當且僅當 G。中 KD = 2，KU = 2，KD = KD = KXG砧）=K（GrA： 1 時，則仏為無結圖。
證明先證充分性。由於G。中（％；%）為不相干點對，故G。中不存在尺。3仏因此，
門 Gab（幻3） = 0？又因為 K{Gab） — 2，Gab（vi） （JGab（t/3） = Gab。由此得 Jab = Gab—Gab{vl） — Gab（v3） =0。同樣可證：當 iC（Gfl？） = 2 時，幾=0；當 K（Gad） = K（GO = K（Gbd） = K（Gcd） = 1 時山
=*，b，— ~ ？，bd ~Jcd= 0 ？？
再證必要性。設G。為無結圖，即G0中J ab — J ac==ZJad = J bc = J bd = Jcd = 0 ？因為由 人*定義知，UGfl*（t/3）==Ga*。又由於 G。中（Pi；t；3）為不相干點對 由此可見Gd是由（^（^和G^（*c；3）兩個連通子圖組成，故K（GU） = 2。同樣，由於J？ = 0，所以 K{Gar） = 2。由於 4=*/如=。八/=二 = 0，所以 K{Gad、= K（Gbc） = K（Gb/）=KiGcd） = 。證畢。
定理2設G。為無結圖，則G。中均為樹 形圖。？
證明G0為無結圖，C。中兩色子圖按它們的連通子圖數目K可分為兩類：和為一 類；Gad，Gbc，Gbd，Gcd為另一類。因此，可從，Gfl*（t；3） ’Gah），Ga<r（z；4）中任取一個作為代表 給予證明。不妨取Gab、xn在另一類中不妨取Gw作為代表。
先證G^t^）是樹形圖。因為G。中^（GJt/O）—；！，所以是連通圖。下面用反證法' 證明G^（%）中不含任一回路。將G。嵌入一個平面，設G^（^）中有一個迴路〇，==（%，如，…， %，tm），C，把4劃分成兩部分。在C。內側可分以下兩種情況：
1）若在C，內側至少有一個點。當其中只要有一個^或⑴色點時，則G。中至少有一個 Jch。當其中只有a（或6，或a，6）色點時，則Go中至少有一個九（或人，或JaM人）和或 ？/&或和那末，上述情況均與G。為無結圖相矛盾。
2）若在C，內側不含任何點。不失一般性，設C，=（如，私2，奶3，認4，叫），它們分別著a，6，a，6， a色。由於尺（G^） = l，故G。中存在一條p；1。i3W。由於7aGk） = l，故在G。中存在一條屍，2。，灰。 又由於C，內側不含任何點，所以P。u。iad和P‘ZMbc都在C，的外側，但它們兩者之間沒有同色 點，從而兩者相交叉，這與G。的平面性相矛盾。綜上分析，Ga4（A）是一個不含任何迴路的連通 圖，故它是樹形圖。仿效上面，可證明Ga4U3），Gah2），〇？（%）也都是樹形圖。
再證是樹形圖。由於尺（0。，）= 1，故是一個連通圖。也用反證法證明中不含任一 迴路。設中有一個迴路（^—（^，？，^^，？，力山它們分別著？^^“⑴色。C，把G。劃分 成兩部分。在C，內側可有以下兩種情況：
1）設C，內側至少有一個點。當其中只要有一個6（或c）色點時，則G。中至少有一個J&。 當其中只有a（或山或a和A色點時，則Gu中至少有一個人4（或？/？，或人4和D和人八或 人/，或九和那末，上述情況均與G。為無結圖相矛盾。
2）設C，內側不含任何點。由於G。中為相干點對，G。中存在一條P3。5W，又由於 Cy內側不含任何點，故P“bd在C，的外側。換言之，C，在中，或在B2中。又由於G。中 K（G^（v2））=K（G。Avi）） = l，^l： Go 中存在一條 Pn。^ac。由於 K（GM） = 1，故 G0 中存在一條
又由於C，內側不含任一點，所以乙和P，2。，M都在C，的外側，但它們間無同色 點，從而兩’者相交叉。這與Gu的平面性相矛盾。由此可見Gw中不含任一回路。
綜上分析，是一個沒有迴路的連通圖，故是一個樹形圖。仿效G&可證明Gfc，GM， 也都是樹形圖。證畢。
定理3設G。為無結圖，若G。中存在準色交錯路徑P1和P3，則P^P3。
證明因為G0為無結圖，所以ODUG^G^G上）門O） = 0。因此，G。中 著a色的點不是在<^（巧）中，就是在GJw）中，G？中著6色的點不是在<^4（13）中，就是在 Ga4（%）中。換言之，a^Ga4（Wl）與aGGa4（%）等價，（巧）與等價。由此得
P1 = P2，i （acbc，b 6 G^iVi） ，a G Ga6^v3））
P3 = PiAkacbc，a 6 Gab{v3） ，b G G^C^i））
顯見，產=屍3。證畢。'
定理4設G。為無結圖，若G。中存在準色交錯路徑屍2和屍4，則屍2 =屍'
可仿效定理3證明，這裡不贅述了。
3例項
假設圖G。如圖1所示。在G。中％，t/2分別著a，a，b，c，d色，它們之間有以下七
條兩色交錯路徑：屍（t/i，取5），屍2，5“d= （口2，取5），屍 2，3 口=ivZyV3） itJ？C= iv39v^） 9P itiaC =ivi ，t；4）{v^^vi^vio^vs） ， P4t5cd= （vi9v6jv7 9v89v9 9v5）。所以（A ？%）， （^z ？%），
（t/2 ？ t/a），（t/3 ？ V4），（Vl ？ t/4） ， （1^3 ？ ”5）和（。4 ？。5）均為相干點對？在{。1 ，。2，。3 9^4 ^5 ）中（口1 fV2 ），
（%；%）和（t；2；w4）均為不相干點對。由圖1可見，在Go中K⑴J = 2，K iG aJ = 2， K iG ad）= KiGbc）=K{Gbds>=Ki。Gcd} = 。故圖是一個無結圖。它的兩色子圖用圖2表示
由圖 2 顯見，Go 的兩色子圖 Gab （% ） ， （jab （D3），Gae （^2 ），Gac （W ） ， Gad，Gbc ， Gbd，均為樹形
再考察圖1的圖G。，可驗證定理3和定理4。因為在G。中屍^產，屍2 =產。具體情況如在圖G。中其中b色點％。屬於Ga*（Pi），a色點和如均 屬+GaA（t；3）。若在GJa）中色交換，會使屍1變成巧和％間％兩色交錯路徑P2，wo若在 GaA（i；3）中色交換，會使屍3變成和％間&兩色交錯路徑P2，J>c。
在圖G。中屍2=屍4=（t^，t/io，t^，t；3），其中c色點％屬於0^（1>2），<2色點％屬於Ga？：（t^）。若 在Ga，（z；2）中色交換，會使P2變成Vl和％間ab兩色交錯路徑/V3M；若在G二（^）中色交換， 會使P4變成A和％間cb兩色交錯路徑1，
本文著重研究了無結圖的充要條件和它的特徵。事實上，無結圖還有一些性質對研究平面圖的著色十分重要，因篇幅所限，本文不宜將它們也展開討論，留待以後再研究。