无结图及其若干性质

　　从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

　　先证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‘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()) = 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>=} = \.故图是一个无结图.它的两色子图用图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\,

　　本文着重研究了无结图的充要条件和它的特征.事实上，无结图还有一些性质对研究平面图的着色十分重要，因篇幅所限，本文不宜将它们也展开讨论，留待以后再研究.