稀疏圖平方圖的染色數上界

張 艷

(天津大學 應用數學中心, 天津 300072)

1 引言與主要結果

本文所考慮的圖均為有限的簡單無向圖.對于一個圖G, 用E(G),V(G)和Δ(G)分別表示圖G的邊集、頂點集和最大度.用d-點、d--點和d+-點分別表示度數為d的點、度數不大于d的點和度數不小于d的點.圖G的k-頂點染色是指映射c:V(G)→{1,2,…,k}; 如果當u～v時, 有c(u)≠c(v), 則稱染色c是正常的[1].圖G的平方G2定義為: 頂點集V(G)=V(G2), 并且uv∈E(G2)當且僅當u和v之間的距離至多為2.平方圖G2的色數是指使得G2存在正常k-染色的最小整數k, 用χ(G2)表示.根據定義, 有χ(G2)≥Δ(G)+1, 其中Δ(G)是指圖G的最大度[2].文獻[3]研究了平面圖的相關性質.

猜想1[4]如果G是一個平面圖, 則:

1) 當Δ(G)=3時, 有χ(G2)≤7;

2) 當4≤Δ(G)≤7時, 有χ(G2)≤Δ(G)+5;

Wegner[4]證明了如果猜想1是正確的, 則χ(G2)的上界是緊的, 并且如果Δ(G)=3, 則χ(G2)≤8.對于超平面圖, 文獻[5]證明了猜想1.但在平面圖中, 該猜想未得到驗證.

圖G的最大平均度定義如下:

(1)

其中V(H)和E(H)分別指子圖H的頂點集和邊集.

定理2[7]設圖G的最大度Δ(G)=Δ, 則有如下結論:

2) 如果mad(G)<3,Δ≠5, 則χ(G2)≤Δ+5; 如果mad(G)<3,Δ=5, 則χ(G2)≤11;

Charpentier猜想[8]: 如果mad(G)<4, 則χ(G2)≤2Δ(G).文獻[9]通過構造圖G, 使得圖G滿足mad(G)<4, 而χ(G2)=2Δ(G)+2, 進而否定了Charpentier猜想.此外, Charpentier[8]還證明了對于充分大的Δ(G), 如果mad(G)<4, 則χ(G2)≤3Δ(G)+3.因此, 有

2Δ(G)+2≤max{χ(G2)|mad(G)<4}≤3Δ(G)+3.

(2)

定理3[8]如果mad(G)<4并且Δ(G)≥8, 則χ(G2)≤3Δ(G)+1.

對于最大度Δ(G)≤5的圖,χ(G2)的上界為3Δ(G)+1, 并且該上界是緊的[8].

定義1在圖G中, 若存在一個頂點的排序σ:v1,v2,…,vn, 使得對任意的vi(2≤i≤n), |vj:vi～vj,j

本文主要結果如下:

定理4如果mad(G)<4且Δ(G)≥7, 則χ(G2)≤3Δ(G)+1.

定理5如果mad(G)≤4且Δ(G)≥8, 則χ(G2)≤3Δ(G)+5.

2 定理4的證明

要證明定理4, 只需證明對任意的圖G滿足mad(G)<4且Δ≥7時,G2是3Δ-退化的即可.用反證法, 假設圖G是滿足mad(G)<4且Δ≥7邊數最少的極小反例,G2不是3Δ-退化的.先令G中每個頂點的初始權重為w(v)=d(v)-4, 由于mad(G)<4, 因而初始總權重為負; 然后利用權轉移規則, 將頂點間的權重進行相互轉移, 計算經過權重轉移后的總權重, 如果是非負的, 則得矛盾.在每個頂點權重轉移過程中, 需找出在圖G中所規避的構型.

2.1 相關命題

定義2設v是圖G的d點, 用di(v)表示點v在圖G中i鄰域的個數(i=2,3).當d(v)≥4時, 對頂點定義如下:

1) 如果d(v)-d2(v)≥7, 則v是好頂點.

2) 如果d(v)-d2(v)=6, 則v是弱好頂點.

3) 如果d(v)-d2(v)=5, 則v是A型弱壞頂點.當d3(v)=0時,v稱為A型第一類的; 當1≤d3(v)≤3時,v稱為A型第二類的.

4) 如果d(v)-d2(v)=4, 則v是B型弱壞頂點.當d3(v)=0時,v稱為B型第一類的; 當d3(v)=1時,v稱為B型第二類的.

5) 如果d(v)-d2(v)=3, 則v是壞頂點.

首先假設圖G是極小反例, 即圖G滿足mad(G)<4并且Δ≥7, 但G2不是3Δ-退化的.根據圖G的極小性, 在圖G中刪除某條uv邊后(Guv)2是3Δ-退化的, 最后只需證明G2是3Δ-退化的, 得矛盾.

命題1圖G中的每個4+-頂點都是定義2中的一種.

證明: 假設G中的頂點v既不是壞頂點, 也不是B型弱壞頂點、A型弱壞頂點、弱好頂點和好頂點, 則根據定義有d(v)-d2(v)≤2, 或者d(v)-d2(v)=4并且d3(v)≥2, 或者d(v)-d2(v)=5并且d3(v)≥4.

對于第一種情形, 因為d(v)≥4, 所以v有2鄰域, 記為w.根據圖G的極小性, (Gvw)2是3Δ-退化的.假設σ是(Gvw)2的好排序, 可先從σ中刪除v及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 排在點v之前出現的鄰域個數至多為2Δ+Δ-2=3Δ-2.對于每個2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是3Δ-退化的, 矛盾.

對于第二種情形, 令w1,w2分別是v的兩個3鄰域.根據圖G的極小性, (Gvw1)2是3Δ-退化的.假設σ是(Gvw1)2的好排序, 可做如下操作: 先從σ中刪除v,w1,w2及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 排在點v之前且與其相鄰的頂點個數至多為2Δ+Δ-4+4=3Δ.對于wi(i=1,2), 出現在其之前且與其相鄰的頂點至多有(2Δ+4)個.最后對于2頂點, 與之相鄰且出現在其之前的頂點個數至多為2Δ.因此G2是3Δ-退化的, 矛盾.

對于第三種情形, 令w1,w2,w3,w4分別是v的3鄰域.根據圖G的極小性, (Gvw1)2是3Δ-退化的.假設σ是(Gvw1)2的好排序, 可做如下操作： 先從σ中刪除v,w1,w2,w3,w4及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 排在點v之前且與其相鄰的頂點個數至多為Δ+Δ-5+8=2Δ+3.對于wi(i=1,2,3,4), 與其相鄰且出現在其之前的頂點個數至多為2Δ+5.最后對于2頂點, 與其相鄰且出現在其之前的頂點至多有2Δ個.因此G2是3Δ-退化的, 矛盾.證畢.

命題2在圖G中, 3--點不與3--點相鄰.

證明: 設u,v是圖G中兩個相鄰的3--點.根據圖G的極小性, (Guv)2是3Δ-退化的.假設σ是(Guv)2的好排序, 可先從σ中刪除u和v, 形成新的排序σ′, 然后在σ′中將u和v依次加回.顯然, 與u相鄰并且排在u前面的頂點個數至多為2Δ+3,v同理.因此G2是3Δ-退化的, 矛盾.證畢.

命題3在圖G中, 壞頂點不與3點相鄰, 并且其4+鄰域點不是壞頂點.

證明： 設v是圖G的壞頂點,u是與v相鄰的3頂點.根據圖G的極小性, (Gvu)2是3Δ-退化的.假設σ是(Gvu)2的好排序, 可先從σ中刪除v和u及v所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回來.首先對于點v, 出現在點v之前且與其相鄰的頂點個數至多為2Δ+Δ-3+2=3Δ-1.對于點u, 排在其之前的鄰域至多有(2Δ+3)個.最后對于2頂點, 排在其之前且與其相鄰的頂點至多有2Δ個.因此G2是3Δ-退化的, 矛盾.

假設x是圖G的壞頂點, 并且x是v的4+鄰域點,w是v的2鄰域.根據圖G的極小性, (Gvw)2是3Δ-退化的.假設σ是(Gvw)2的好排序, 可先從σ中刪除v及v和x所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 排在點v之前且與其相鄰的頂點個數至多為2Δ+Δ-3+3=3Δ.對于(2Δ-6)個2鄰域的每個點, 與之相鄰且排在其之前的頂點個數至多為Δ+4+2Δ-6=3Δ-2.因此G2是3Δ-退化的, 矛盾.證畢.

命題4如果v是圖G中B型弱壞頂點u的壞鄰域, 則v至少有2個好鄰域.

證明: 假設w(w≠u)是v的鄰域, 并且w不是好頂點.因為v是壞鄰域, 所以v有2鄰域x.根據圖G的極小性, (Gvx)2是3Δ-退化的.假設σ是(Gvx)2的好排序, 可先從σ中刪除點v及v和w所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.首先對于點v, 與點v相鄰并且排在之前的頂點個數至多為

Δ-3+4+Δ+d(w)-d2(w)=2Δ+1+d(w)-d2(w)≤2Δ+7

(因為w不是好頂點, 所以d(w)-d2(w)≤6).此外, 與2頂點相鄰且排在其之前的頂點至多有2Δ個.因此G2是3Δ-退化的, 矛盾.證畢.

命題5在圖G中, 每個B型第一類的弱壞頂點至多有2個壞鄰域.

證明: 設u是B型第一類的弱壞頂點, 假設u至少有3個壞鄰域, 記為v1,v2,v3.由圖G的極小性, (Guv1)2是3Δ-退化的.假設σ是(Guv1)2的好排序, 可先從σ中刪除u,v1,v2,v3及其所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于vi(i=1,2,3), 排在vi之前且與其相鄰的頂點個數至多為2Δ+Δ-3+3=3Δ.對于點u, 與之相鄰且排在之前的頂點個數至多為Δ-4+Δ+3×3=2Δ+5.對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是3Δ-退化的, 矛盾.證畢.

命題6在圖G中, 沒有好鄰域但有壞鄰域的B型第一類弱壞頂點至少有1個弱好鄰域.

證明: 設u是沒有好鄰域但有壞鄰域的B型第一類弱壞頂點, 且u沒有弱好鄰域, 記其中的1個壞鄰域為v1, 其他鄰域為v2,v3,v4.由圖G的極小性, (Guv1)2是3Δ-退化的.假設σ是(Guv1)2的好排序, 可做如下操作: 先從σ中刪除u,v1及u,v1,v2,v3,v4所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.首先對于v1, 排在其之前且與其相鄰的頂點個數至多為2Δ+Δ-3+3=3Δ.對于點u, 與u相鄰且排在其之前的頂點個數至多為

(因為vi(i=2,3,4)既不是好鄰域也不是弱好鄰域, 所以d(vi)-d2(vi)≤5).最后對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是3Δ-退化的, 矛盾.證畢.

命題7每個B型第二類的弱壞頂點至多有1個壞鄰域.

證明: 設u是B型第二類的弱壞頂點, 且u至少有2個壞鄰域, 記為v1和v2, 令w是u的3鄰域.由圖G的極小性, (Guw)2是3Δ-退化的.假設σ是(Guw)2的好排序, 可做如下操作： 先從σ中刪除u和w及u,v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.首先對于點u, 與u相鄰且排在其之前的頂點個數至多為Δ-4+Δ+2×3+2=2Δ+4.其次, 對于3頂點w, 與w相鄰且排在其之前的頂點至多有(2Δ+4)個.最后對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是3Δ-退化的, 矛盾.證畢.

命題8在圖G中, 沒有好鄰域的B型第二類弱壞頂點至少有2個弱好鄰域; 有壞鄰域且僅有1個好鄰域的B型第二類弱壞頂點至少有1個弱好鄰域.

證明: 設u是圖G中沒有好鄰域的B型第二類弱壞頂點, 且u至多有1個弱好鄰域.令w是u的3鄰域, 其他鄰域為vi(i=1,2,3).由圖G的極小性, (Guw)2是3Δ-退化的.假設σ是(Guw)2的好排序, 可做如下操作: 先從σ中刪除u和w及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.如果u有1個弱好鄰域, 記為v1, 則與u相鄰且排在u之前的頂點個數至多為

Δ-2+d(v1)-d2(v1)+d(v2)-d2(v2)+d(v3)-d2(v3)≤Δ-2+6+2×5=Δ+14

(因為vi(i=2,3)既不是好鄰域也不是弱好鄰域, 所以d(vi)-d2(vi)≤5); 如果u沒有弱好鄰域, 則與u相鄰且排在其之前的頂點個數至多為

Δ-2+d(v1)-d2(v1)+d(v2)-d2(v2)+d(v3)-d2(v3)≤Δ-2+5×3=Δ+13

(因為vi(i=1,2,3)既不是好鄰域也不是弱好鄰域, 所以d(vi)-d2(vi)≤5).此外, 對于3頂點w, 與w相鄰且排在其之前的頂點至多有(2Δ+4)個.對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是3Δ-退化的, 矛盾.

同理, 設u′是圖G中有壞鄰域且僅有1個好鄰域的B型第二類弱壞頂點, 且u′不存在弱好鄰域.令w′是u′的3鄰域, 其他鄰域為其中是u′唯一的好鄰域,是u′的壞鄰域.因為u′不存在弱好鄰域, 所以既不是好頂點也不是弱好頂點.由圖G的極小性, (Gu′w′)2是3Δ-退化的.假設σ是(Gu′w′)2的好排序, 可做如下操作： 先從σ中刪除u′和w′及所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點u′, 與u′相鄰且排在其之前的頂點個數至多為

命題9在圖G中, 設A型第一類弱壞頂點為u, 且其鄰域為vi(i=1,2,3,4,5).令a=|{vi:vi是有2個好鄰域的壞頂點}|,b=|{vi:vi是至多有1個好鄰域的壞頂點}|, 則有以下幾種情形:

1) 當a=0時,b≤3;

2) 當a=1時,b≤2;

3) 當a=2時,b≤2;

4) 當a=3時,b≤1.

證明: 1) 當a=0時, 假設b≥4, 令至多有1個好鄰域的壞頂點分別為v1,v2,v3,v4, 并且u與vi(i=1,2,3,4)相鄰.根據圖G的極小性, (Guv1)2是3Δ-退化的.假設σ是(Guv1)2的好排序, 可先從σ中刪除u,v1,v2,v3,v4及其所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.因為vi(i=1,2,3,4)是至多有1個好鄰域的壞頂點, 所以vi存在不是好頂點的鄰域, 記為zi.在尋找與vi相鄰且排在其之前頂點的個數時需刪除zi的2鄰域.在σ′中, 與vi相鄰且排在其之前的頂點個數至多為

Δ-3+4+Δ+d(zi)-d2(zi)≤2Δ+1+6=2Δ+7≤3Δ

(因為zi不是好頂點, 所以d(zi)-d2(zi)≤6).對于點u, 與u相鄰且排在其之前的頂點個數至多為Δ-5+Δ+4×3=2Δ+7.對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是3Δ-退化的, 矛盾.

2) 當a=1時, 假設b≥3, 令有2個好鄰域的壞頂點為v1, 至多有1個好鄰域的壞頂點為v2,v3,v4, 并且u與vi(i=1,2,3,4)相鄰.根據圖G的極小性, (Guv2)2是3Δ-退化的.假設σ是(Guv2)2的好排序, 可先從σ中刪除u,v2,v3,v4及其與v1所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.因為vi(i=2,3,4)是至多有1個好鄰域的壞頂點, 與第一種情形類似.對于u, 在σ′中, 與u相鄰且排在其之前的頂點個數至多為Δ-5+Δ+4×3=2Δ+7.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是3Δ-退化的, 矛盾.

3) 當a=2時, 假設b≥3, 令有2個好鄰域的壞頂點為v1和v2, 至多有1個好鄰域的壞頂點為v3,v4,v5, 并且u與vi(i=1,2,3,4,5)相鄰.根據圖G的極小性,(Guv3)2是3Δ-退化的.假設σ是(Guv3)2的好排序, 可先從σ中刪除u,v3,v4,v5及其與v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.因為vi(i=3,4,5)是至多有一個好鄰域的壞頂點, 與第一種情形類似.在σ′中, 對于u, 與u相鄰且排在其之前的頂點個數至多為Δ-5+5×3=Δ+10.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是3Δ-退化的, 矛盾.

4) 當a=3時, 假設b=2, 令有2個好鄰域的壞頂點為v1,v2,v3, 至多有1個好鄰域的壞頂點為v4和v5, 并且u與vi(i=1,2,3,4,5)相鄰.根據圖G的極小性, (Guv4)2是3Δ-退化的.假設σ是(Guv4)2的好排序, 可先從σ中刪除u,v4,v5及其與v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.因為vi(i=4,5)是至多有1個好鄰域的壞頂點, 與第一種情形類似.在σ′中, 對于u, 與u相鄰且排在其之前的頂點個數至多為Δ-5+5×3=Δ+10.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是3Δ-退化的, 矛盾.證畢.

命題10設u是圖G中A型第二類的弱壞頂點, 當d3(u)=1時,u至多有2個壞鄰域; 當d3(u)=2時,u至多有一個壞鄰域; 當d3(u)=3時,u沒有壞鄰域.

證明: 當d3(u)=1時, 假設u至少有3個壞鄰域v1,v2,v3, 且u的3鄰域為x.根據圖G的極小性, (Gux)2是3Δ-退化的.假設σ是(Gux)2的好排序, 可先從σ中刪除u和x及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于u, 與u相鄰且排在其之前的頂點個數至多為Δ-5+Δ+3×3+2=2Δ+6.對于3度頂點x, 與之相鄰且排在其之前的頂點至多有(2Δ+5)個.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是3Δ-退化的, 矛盾.

當d3(u)=2時, 假設u至少有2個壞鄰域v1,v2, 且u的2個3鄰域分別為w1和w2.根據圖G的極小性, (Guw1)2是3Δ-退化的.假設σ是(Guw1)2的好排序, 可先從σ中刪除u,w1,w2及u,v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于u, 與u相鄰且排在其之前的頂點個數至多為Δ-5+Δ+2×3+2×2=2Δ+5.對于wi(i=1,2), 與之相鄰且排在其之前的頂點至多有(2Δ+5)個.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是3Δ-退化的, 矛盾.

當d3(u)=3時, 假設u存在壞鄰域v1, 令u的3鄰域分別為w1,w2,w3.根據圖G的極小性, (Guw1)2是3Δ-退化的.假設σ是(Guw1)2的好排序, 可先從σ中刪除u,w1,w2,w3及u和v1所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于u, 與u相鄰且排在其之前的頂點個數至多為Δ-5+Δ+3+2×3=2Δ+4.對于wi(i=1,2,3), 與之相鄰且排在其之前的頂點至多有(2Δ+5)個.最后對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是3Δ-退化的, 矛盾.證畢.

2.2 權轉移規則

因為mad(G)<4, 所以有

(3)

令每個頂點的初始權重為w(v)=d(v)-4, 易知圖G的初始總權重是負的.下面制定一些權重轉移規則, 使得頂點間經過權重轉移后, 圖G中每個頂點的權重是非負的, 進而圖G的總權重是非負的, 形成矛盾.

下面計算經過權重轉移后各頂點的最終權重.

2.2.1 3--點 根據權轉移規則1,G中的每個2頂點會從其每個鄰域接收1的權重, 而且不會失去任何權重, 因此其最終權重是w′(v)=2-4+2×1=0.

2.2.2 壞頂點 令v是圖G的壞頂點, 根據權轉移規則1,v將權重給相鄰的2鄰域后,v的剩余權重為-1.此外, 注意到壞頂點不是好頂點和弱好頂點, 根據命題3,v不與3點相鄰并且v沒有壞鄰域, 因此v不會再失去任何權重.

2.2.3B型弱壞頂點 令v是圖G的B型弱壞頂點.

1) 如果v是B型第一類的, 則根據權轉移規則1,v將權重給相鄰的2鄰域后,v的剩余權重是0.如果v沒有壞鄰域, 則v不會再失去任何權重,v的權重是非負的; 如果v有壞鄰域, 則根據命題4和命題5,v至多有2個壞鄰域, 而且這2個壞鄰域都至少有2個好鄰域, 由權轉移規則4,v最多再失去的權重.此時, 若v有好鄰域, 則根據權轉移規則5,v會接收來自好鄰域的權重, 因此其最終權重是非負的.否則,v沒有好鄰域但v有壞鄰域, 根據命題6,v至少有一個弱好鄰域, 由權轉移規則6,v會接收來自弱好鄰域的權重, 因此其最終權重也是非負的.

2) 如果v是B型第二類的, 則根據權轉移規則1,v將權重給相鄰的2鄰域和3鄰域后, 其剩余權重是如果v沒有壞鄰域, 此時若v有好鄰域, 由權轉移規則5,v接收來自好鄰域的權重, 則v的最終權重是非負的; 否則v沒有好鄰域, 根據命題8,v至少有2個弱好鄰域, 再根據權轉移規則6,v會接收來自弱好鄰域的權重, 因此v的最終權重也是非負的; 如果v有壞鄰域, 則根據命題4和命題7,v至多有1個壞鄰域, 而且這個壞鄰域至少有2個好鄰域, 由權轉移規則4,v最多需給壞鄰域的權重.此時, 若v至少有2個好鄰域, 則根據權轉移規則5,v接收來自好鄰域的權重, 因此v的最終權重是非負的.否則, 若v有1個好鄰域且v有壞鄰域, 則根據命題8及權轉移規則5,6,v至少有1個弱好鄰域, 因此v會分別接收來自好鄰域的權重及弱好鄰域的權重,v的最終權重是非負的; 若v沒有好鄰域, 則根據命題8,v至少有2個弱好鄰域, 由權轉移規則6, 其會接收來自弱好鄰域的權重, 因此其最終權重仍是非負的.

2.2.4A型弱壞頂點 令v是圖G的A型弱壞頂點.

1) 如果v是A型第一類的, 則根據權轉移規則1,v將權重給相鄰的2鄰域后, 其剩余權重是1.令

a=|{vi:vi～v, 且vi是有2個好鄰域的壞頂點}|,

b=|{vi:vi～v, 且vi是至多有1個好鄰域的壞頂點}|.

2) 如果v是A型第二類的, 則當d3(v)=1時, 根據權轉移規則1,v將權重給相鄰的2鄰域和3鄰域后, 其剩余權重是根據命題10,v至多有2個壞鄰域, 再由權轉移規則3,4,v最多會失去的權重, 因此其最終權重是非負的; 當d3(v)=2時, 根據權轉移規則1,v將權重給相鄰的2鄰域和3鄰域后, 其剩余權重是根據命題10,v至多有1個壞鄰域, 再由權轉移規則3,4,v最多會失去的權重, 因此其最終權重是非負的; 當d3(v)=3時, 根據權轉移規則1,v將權重給相鄰的2鄰域和3鄰域后, 其剩余權重是0.根據命題10,v沒有壞鄰域, 不會再失去權重, 因此v的最終權重為0.

綜上可見,v的最終權重是非負的.

2.2.5 弱好頂點 令v是圖G的弱好頂點.根據權轉移規則1,v將權重給相鄰的2鄰域后, 此時v的剩余權重為2.因為v不是好頂點, 根據權轉移規則1,3,4,6, 所以v會將權重給3鄰域、壞鄰域及與之相鄰的B型弱壞頂點.因為d(v)-d2(v)=6, 所以v至多會失去的權重, 因此v的最終權重是非負的.

2.2.6 好頂點 令v是圖G的好頂點, 且記d2(v)是v的2鄰域的個數.根據權轉移規則1,2,3,5, 因為v是好頂點, 所以至多有(d(v)-d2(v))個鄰域分別會接收來自v的至多的權重, 因此其最終權重為

(因為d(v)-d2(v)≥7).

通過上述對頂點間的權重轉移, 可得圖G中每個頂點的最終權重為非負的, 因此圖G的最終總權重也是非負的, 與初始總權重是負的矛盾.

3 定理5的證明

定理5的證明類似定理4, 需找出在圖G中規避的構型.

3.1 相關命題

定義3設v是圖G的d點, 用di(v)表示點v在圖G中i鄰域的個數(i=2,3,4).當d(v)≥5時, 對頂點定義如下:

1) 如果d(v)-d2(v)≥8, 則v是優頂點.

2) 如果d(v)-d2(v)≥7, 則v是好頂點.

3) 如果d(v)-d2(v)=6, 則v是弱好頂點.

4) 如果d(v)-d2(v)=5, 則v是A型弱壞頂點.當d3(v)=0時,v稱為A型第一類的; 當1≤d3(v)≤2時,v稱為A型第二類的.

5) 如果d(v)-d2(v)=4, 則v是B型弱壞頂點.當d3(v)=0時,v稱為B型第一類的; 當d3(v)=1時,v稱為B型第二類的.

6) 如果d(v)-d2(v)=3, 則v是壞頂點.

首先假設圖G是極小反例, 即圖G滿足mad(G)≤4且Δ≥8, 但G2不是(3Δ+4)-退化的.根據圖G的極小性, 在圖G中刪除某條uv邊后(Guv)2是(3Δ+4)-退化的, 最后只需證明G2是(3Δ+4)-退化的, 得到矛盾.

命題11圖G中的每個5+-頂點都是定義3中的一種.

證明: 假設圖G中的頂點v既不是壞頂點, 也不是A型弱壞頂點、B型弱壞頂點、弱好頂點和好頂點, 則根據定義有d(v)-d2(v)≤2, 或者d(v)-d2(v)=4并且d3(v)≥2, 或者d(v)-d2(v)=5并且d3(v)≥3.

對于第一種情形, 因為d(v)≥5, 所以v有2° 鄰域, 記為w.根據圖G的極小性, (Gvw)2是(3Δ+4)-退化的.假設σ是(Gvw)2的好排序, 可先從σ中刪除v及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 排在點v之前出現的鄰域個數至多為2Δ+Δ-2=3Δ-2.對于每個2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

對于第二種情形, 令w1,w2分別是v的2個3鄰域.根據圖G的極小性, (Gvw1)2是(3Δ+4)-退化的.假設σ是(Gvw1)2的好排序, 可先從σ中刪除v,w1,w2及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 排在點v之前且與其相鄰的頂點個數至多為2Δ+Δ-4+4=3Δ.對于wi(i=1,2), 排在其之前且與其相鄰的頂點個數至多為2Δ+4.對于2頂點, 與之相鄰且出現在其之前的頂點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.

對于第三種情形, 令w1,w2,w3分別是v的3鄰域.根據圖G的極小性, (Gvw1)2是(3Δ+4)-退化的.假設σ是(Gvw1)2的好排序, 可先從σ中刪除v,w1,w2,w3及v的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 出現在點v之前且與其相鄰的頂點個數至多為2Δ+Δ-5+6=3Δ+1.對于wi(i=1,2,3), 出現在其之前的鄰域個數至多為2Δ+5.對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題12在圖G中, 4--點不與4--點相鄰.

證明: 設u,v是圖G中兩個相鄰的4--頂點.根據圖G的極小性, (Guv)2是(3Δ+4)-退化的.假設σ是(Guv)2的好排序, 可先從σ中刪除u和v, 形成新的排序σ′, 然后在σ′中將u和v依次加回.顯然, 對于點u, 與u相鄰并且排在其之前的頂點至多有(3Δ+4)個,v同理.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題13在圖G中, 壞頂點v既不與3點相鄰也不與4點相鄰, 并且v的5+鄰域點不是壞頂點.

證明: 設u是與v相鄰的3頂點.根據圖G的極小性, (Gvu)2是(3Δ+4)-退化的.假設σ是(Gvu)2的好排序, 可先從σ中刪除v和u及v所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 出現在v之前且與其相鄰的頂點個數至多為2Δ+Δ-3+2=3Δ-1.對于3點u, 排在u之前的鄰域至多有(2Δ+3)個.對于2頂點, 排在其之前且與其相鄰的點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.

設w是與v相鄰的4頂點.根據圖G的極小性, (Gvw)2是(3Δ+4)-退化的.假設σ是(Gvw)2的好排序, 可先從σ中刪除v和w及v所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 排在點v之前且與其相鄰的頂點個數至多為2Δ+Δ-3+3=3Δ.對于4點w, 排在w之前的鄰域至多有(3Δ+3)個.對于2頂點, 排在其之前且與其相鄰的點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.

假設x是圖G中的壞頂點, 并且x是v的5+鄰域點,w是v的2鄰域.根據圖G的極小性, (Gvw)2是(3Δ+4)-退化的.假設σ是(Gvw)2的好排序, 可先從σ中刪除v及v和x所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點v, 排在點v之前且與其相鄰的頂點個數至多為2Δ+Δ-3+3=3Δ.對于(2Δ-6)個2鄰域的每個點, 與之相鄰且出現在其之前的頂點個數至多為Δ+4+2Δ-6=3Δ-2.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題14如果v是圖G中A型弱壞頂點u的壞鄰域, 則v至少有2個優鄰域.同理, 若v′是圖G中B型弱壞頂點u′的壞鄰域, 則v′至少有2個優鄰域.

證明: 假設w(w≠u)是v的鄰域, 并且w不是優頂點.因為v是壞鄰域, 所以v有2鄰域x.根據圖G的極小性, (Gvx)2是(3Δ+4)-退化的.假設σ是(Gvx)2的好排序, 可先從σ中刪除v及v和w所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.首先對于點v, 與v相鄰并且排在其之前的頂點個數至多為

Δ-3+5+Δ+d(w)-d2(w)≤ 2Δ+2+7=2Δ+9

(因為w不是優頂點, 所以d(w)-d2(w)≤7).此外, 與2頂點相鄰且排在其之前的頂點個數至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

同理可證v′至少有2個優鄰域.證畢.

命題15每個B型第一類的弱壞頂點至多有2個壞鄰域.

證明: 設u是B型第一類的弱壞頂點, 且u至少有3個壞鄰域, 分別記為v1,v2,v3.因為u是B型第一類弱壞頂點, 所以u有2鄰域x, 由圖G的極小性, (Gux)2是(3Δ+4)-退化的.假設σ是(Gux)2的好排序, 可先從σ中刪除u及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點u, 與之相鄰且排在其之前的頂點個數至多為Δ-4+Δ+3×3=2Δ+5.對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題16在圖G中, 沒有好鄰域的B型第一類弱壞頂點至少有1個弱好鄰域; 沒有好鄰域但至少有1個弱好鄰域的B型第一類弱壞頂點至多有1個壞鄰域.

證明: 設u是沒有好鄰域的B型第一類弱壞頂點, 且u沒有弱好鄰域, 其鄰域設為v1,v2,v3,v4.因為u是B型第一類弱壞頂點, 所以u有2鄰域x, 由圖G的極小性, (Gux)2是(3Δ+4)-退化的.假設σ是(Gux)2的好排序, 可先從σ中刪除u及u,v1,v2,v3,v4所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點u, 與u相鄰且排在其之前的頂點個數至多為

(因為vi(i=1,2,3,4)既不是弱好鄰域也不是好鄰域, 所以d(vi)-d2(vi)≤5).對于2頂點, 與之相鄰且排在其之前的點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.

設沒有好鄰域但至少有1個弱好鄰域的B型第一類弱壞頂點為u′, 且其至少有2個壞鄰域v1和v2, 其他鄰域為z和w, 其中z是弱好鄰域.因為u′是B型第一類弱壞頂點, 所以u′有2鄰域x′, 由圖G的極小性, (Gu′x′)2是(3Δ+4)-退化的.假設σ是(Gu′x′)2的好排序, 可先從σ中刪除u′及u′,w,v1,v2,z所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于u′, 與u′相鄰且排在其之前的頂點個數至多為

(因為w不是好鄰域, 所以d(w)-d2(w)≤6).對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題17在圖G中, 每個B型第二類的弱壞頂點u至少有1個好鄰域, 此外u至多有1個壞鄰域.

證明: 設u沒有好鄰域, 令w是u的3鄰域, 其他鄰域為v1,v2,v3.由圖G的極小性, (Guw)2是(3Δ+4)-退化的.假設σ是(Guw)2的好排序, 可先從σ中刪除u和w及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點u, 與u相鄰且排在其之前的頂點個數至多為

Δ-4+2+d(v1)-d2(v1)+d(v2)-d2(v2)+d(v3)-d2(v3)≤Δ-2+6×3=Δ+16

(因為vi(i=1,2,3)不是好頂點, 所以d(vi)-d2(vi)≤6).此外, 對于3頂點w, 與w相鄰且排在其之前的頂點至多有(2Δ+4)個.對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.

設u至少有2個壞鄰域, 記為v1和v2.由圖G的極小性, (Guw)2是(3Δ+4)-退化的.假設σ是(Guw)2的好排序, 可先從σ中刪除u和w及u,v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于u, 與u相鄰且排在其之前的頂點個數至多為

Δ-4+2+d(v1)-d2(v1)+d(v2)-d2(v2)+Δ=2Δ+4.

命題18在圖G中, 有且僅有1個好鄰域的B型第二類弱壞頂點至少有1個弱好鄰域.

證明: 設u是有且僅有1個好鄰域的B型第二類弱壞頂點, 且u沒有弱好鄰域, 令w是u的3鄰域,v1為u的好鄰域, 其他鄰域為v2和v3.由圖G的極小性, (Guw)2是(3Δ+4)-退化的.假設σ是(Guw)2的好排序, 可先從σ中刪除u和w及u,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點u, 與u相鄰且排在其之前的頂點個數至多為

Δ-4+2+Δ+d(v2)-d2(v2)+d(v3)-d2(v3)≤Δ-2+Δ+2×5=2Δ+8

(因為vi(i=2,3)既不是好鄰域又不是弱好鄰域, 所以d(vi)-d2(vi)≤5).此外, 對于3頂點w, 與w相鄰且排在其之前的頂點至多有(2Δ+4)個.對于2頂點, 與之相鄰且排在其之前的頂點至多有2Δ個.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題19在圖G中, 每個A型第一類的弱壞頂點至多有4個壞鄰域.

證明: 設u是圖G中A型第一類的弱壞頂點, 且u至少有5個壞鄰域v1,v2,v3,v4,v5.根據圖G的極小性, (Guv1)2是(3Δ+4)-退化的.假設σ是(Guv1)2的好排序, 可先從σ中刪除u,v1,v2,v3,v4,v5及其所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于vi(i=1,2,3,4,5), 與之相鄰且排在其之前的頂點個數至多為2Δ+Δ-3+4=3Δ+1.對于u, 與u相鄰且排在其之前的頂點至多有(Δ-5+5×3=Δ+10)個.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題20設u是圖G中A型第二類的弱壞頂點, 當d3(u)=1時,u至多有2個壞鄰域; 當d3(u)=2時,u至多有1個壞鄰域.

證明: 當d3(u)=1時, 假設u至少有3個壞鄰域v1,v2,v3, 記u的3鄰域為x.根據圖G的極小性, (Gux)2是(3Δ+4)-退化的.假設σ是(Gux)2的好排序, 先從σ中刪除u和x及u,v1,v2,v3所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點u, 與u相鄰且排在其之前的頂點個數至多為Δ-5+Δ+3×3+2=2Δ+6.對于3點x, 與之相鄰且排在其之前的頂點至多有(2Δ+5)個.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

當d3(u)=2時, 假設u至少有2個壞鄰域v1,v2, 記u的3鄰域分別為w1和w2.根據圖G的極小性, (Guw1)2是(3Δ+4)-退化的.假設σ是(Guw1)2的好排序, 先從σ中刪除u,w1,w2及u,v1,v2所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于點u, 與u相鄰且排在其之前的頂點個數至多為Δ-5+Δ+2×3+2×2=2Δ+5.對于3點wi(i=1,2), 與之相鄰且排在其之前的頂點至多有(2Δ+5)個.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.證畢.

命題21設u是圖G的弱好頂點, 除u的2鄰域外,u的其他鄰域有以下幾種情形:

1) 若u的鄰域中不存在B型弱壞頂點, 則u至多有5個鄰域或者是3頂點或者是壞頂點;

2) 若u的鄰域中存在1個B型弱壞頂點, 則u至多有4個鄰域或者是3頂點或者是壞頂點;

3) 若u的鄰域中存在2個B型弱壞頂點, 則u至多有3個鄰域或者是3頂點或者是壞頂點;

4) 若u的鄰域中存在3個B型弱壞頂點, 則u至多有2個鄰域或者是3頂點或者是壞頂點;

5) 若u的鄰域中存在4個B型弱壞頂點, 則u至多有1個鄰域或者是3頂點或者是壞頂點;

6) 若u的鄰域中存在5個B型弱壞頂點, 則u的鄰域中不存在3頂點或者是壞頂點.

證明: 1) 若弱好頂點u不存在B型弱壞鄰域, 則假設u至少有6個鄰域v1,v2,v3,v4,v5,v6, 分別是3頂點或者是壞頂點.如果v1是3頂點, 則根據圖G的極小性, (Guv1)2是(3Δ+4)-退化的, 故假設σ是(Guv1)2的好排序; 否則,v1是壞頂點, 其2鄰域w, 根據圖G的極小性, (Gv1w)2是(3Δ+4)-退化的, 故假設σ是(Gv1w)2的好排序.在這兩種情形下, 均可從σ中刪除u,v1,v2,v3,v4,v5,v6及其所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于vi中的壞頂點, 假設vi(i=1,2,3,4,5,6)是壞頂點, 與vi相鄰且排在其之前的頂點個數至多為2Δ+5+Δ-3=3Δ+2.對于點u, 在σ′中, 與u相鄰且排在其之前的頂點個數至多為Δ-6+6×3=Δ+12.對于vi中剩余的3點, 與之相鄰且排在其之前的頂點至多有(2Δ+6)個.對于所有剩余的2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

2) 若弱好頂點u有1個B型弱壞鄰域, 則假設u至少有5個鄰域是3頂點或者是壞頂點, 記為v1,v2,v3,v4,v5.如果v1是3頂點, 則根據圖G的極小性, (Guv1)2是(3Δ+4)-退化的, 故假設σ是(Guv1)2的好排序; 否則,v1是壞頂點, 其有2鄰域w, 根據圖G的極小性, (Gv1w)2是(3Δ+4)-退化的, 故假設σ是(Gv1w)2的好排序.在這兩種情形下, 均可從σ中刪除u、3頂點和壞頂點及其與B型弱壞頂點所有的2鄰域, 形成新的排序σ′, 然后在σ′中將刪除的點依次加回.對于vi中的壞頂點, 同1).對于點u, 在σ′中, 與u相鄰且排在其之前的頂點個數至多為Δ-6+1×4+3×5=Δ+13.對于vi中剩余的3點, 與之相鄰且排在其之前的頂點至多有(2Δ+6)個.對于2頂點, 與之相鄰且排在其之前的頂點個數至多為2Δ.因此G2是(3Δ+4)-退化的, 矛盾.

3)～6)的證明同2), 故略.

3.2 權轉移規則

因為mad(G)≤4, 所以有

(4)

令每個頂點的初始權重為w(v)=d(v)-4, 則易知圖G的初始總權重是非正的.通過制定一些權重轉移規則, 使得頂點間經過權重轉移后, 圖G中每個頂點的權重為正, 進而圖G的最終總權重為正, 構成矛盾.

對于圖G中的點v,d2(v)和d4(v)分別表示點v的2鄰域和4鄰域的個數.令當ε1,ε2取足夠小時, 有由D2和D4的定義, 對于任意的點v, 滿足從而可知也成立.

權轉移規則7: 每個頂點給權重1+ε1到其每個2鄰域, 給權重到其每個3鄰域及給權重ε2到其每個4鄰域.

下面計算經過權重轉移后各頂點的最終權重.

3.2.1 4--點 根據權轉移規則7,G中的每個2頂點會從其每個鄰域接收1+ε1的權重, 而且不會失去任何權重, 因此其最終權重是w′(v)=2-4+2×(1+ε1)=2ε1>0.

3.2.2 壞頂點 令v是圖G的壞頂點.根據權轉移規則7,v將權重給相鄰的2鄰域后, 此時v的剩余權重為-1-d2(v)ε1.此外, 注意到壞頂點不是好頂點和弱好頂點,根據命題13,v不與3頂點和4頂點相鄰, 并且v沒有壞鄰域, 因此v不會再失去任何權重.

綜上所述,v的最終權重為正.

3.2.3B型弱壞頂點 令v是圖G的B型弱壞頂點.

1) 如果v是B型第一類的, 則根據權轉移規則7,v將權重給相鄰的2鄰域和4鄰域后,v的剩余權重是-d2(v)ε1-d4(v)ε2.此外, 根據命題14和命題15,v至多有2個壞鄰域, 且每個壞鄰域至少有2個優鄰域, 由權轉移規則10,v至多會失去的權重.如果v有好鄰域, 則根據權轉移規則11,v至少會接收來自好鄰域的權重, 因此v的最終權重是

2) 如果v是B型第二類的, 則根據權轉移規則7,v將權重給相鄰的2鄰域、3鄰域和4鄰域后, 其剩余權重是根據命題14和命題17,v至多有1個壞鄰域, 而且壞鄰域至少有2個優鄰域, 由權轉移規則10,v至多會失去的權重.如果v至少有2個好鄰域, 則由權轉移規則11,v至少會接收來自其好鄰域的權重, 因此v的最終權重是

3.2.4A型弱壞頂點 令v是圖G的A型弱壞頂點.

1) 如果v是A型第一類的, 則根據權轉移規則7,v將權重給相鄰的2鄰域和4鄰域后, 其剩余權重是1-d2(v)ε1-d4(v)ε2.根據命題14和命題19,v至多有4個壞鄰域, 而且壞鄰域至少有2個優鄰域, 由權轉移規則10,v最多會失去的權重, 因此其最終權重是

2) 如果v是A型第二類的, 則當d3(v)=1時, 根據權轉移規則7,v將權重給相鄰的2鄰域、3鄰域和4鄰域后, 其剩余權重是根據命題14和命題20,v至多有2個壞鄰域, 而且壞鄰域至少有2個優鄰域, 再由權轉移規則10,v至多會失去的權重, 故其最終權重是

當d3(v)=2時, 根據權轉移規則7,v將權重給相鄰的2鄰域、3鄰域和4鄰域后, 其剩余權重是-d2(v)ε1-d4(v)ε2.根據命題14和命題20,v至多有1個壞鄰域, 而且壞鄰域至少有2個優鄰域, 再由權轉移規則10,v至多會失去的權重, 故其最終權重是

3.2.5 弱好頂點 令v是圖G的弱好頂點.根據權轉移規則7,v將權重給相鄰的2鄰域和4鄰域后, 此時v的剩余權重是2-d2(v)ε1-d4(v)ε2.因為v不是好頂點, 所以根據權轉移規則7,9,10,12,v會將權重給3鄰域、壞鄰域及給與之相鄰的B型弱壞頂點.若v的鄰域中不存在B型弱壞頂點, 則根據命題21中1),v至多有5個鄰域是3頂點或者是壞頂點.根據權轉移規則7,9,10,v最多會失去的權重, 因此v的最終權重是

若v的鄰域中存在1個B型弱壞頂點, 則根據命題21中2),v至多有4個鄰域是3頂點或者是壞頂點, 根據權轉移規則7,9,10,12,v最多會失去的權重, 因此v的最終權重是

若v的鄰域中存在2個B型弱壞頂點, 則根據命題21中3),v至多有3個鄰域是3頂點或者是壞頂點, 根據權轉移規則7,9,10,12,v最多會失去的權重, 因此v的最終權重是

若v的鄰域中存在3個B型弱壞頂點, 則根據命題21中4),v至多有2個鄰域是3頂點或者是壞頂點, 根據權轉移規則7,9,10,12,v最多會失去的權重, 因此v的最終權重是

若v的鄰域中存在4個B型弱壞頂點, 則根據命題21中5), 則v至多有1個鄰域是3頂點或者壞頂點, 根據權轉移規則7,9,10,12,v最多會失去的權重, 因此v的最終權重是

若v的鄰域中存在5個B型弱壞頂點, 則根據命題21中6),v不存在3鄰域或者是壞鄰域, 根據權轉移規則12,v會失去的權重, 因此v的最終權重是

綜上所述,v的最終權重為正.

3.2.6 好頂點 令v是圖G的好頂點, 并且記d2(v)是v的2鄰域個數.如果v不是優頂點, 則對于除去2鄰域外的其他(d(v)-d2(v))個鄰域, 根據權轉移規則7,9,10,11,v會分別給每個鄰域至多的權重, 因此其最終權重是

(因為d(v)-d2(v)≥8).

通過上述對頂點間的權重轉移, 得到圖G中每個頂點的最終權重為正, 因此圖G的最終總權重也為正, 與初始總權重非正矛盾.

衷心感謝天津大學應用數學中心彭興老師的鼓勵和指導.