最大度為6的圖G的鄰點(diǎn)可區(qū)別邊色數(shù)的一個(gè)上界

吳燕青

(山西師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,山西臨汾 041000)

1 引言

本文主要考慮不含孤立邊的有限簡(jiǎn)單圖.對(duì)圖G,用V(G),E(G),?(G)和mad(G)分別表示圖G的頂點(diǎn)集,邊集,最大度和最大平均度.在G中,用NG(v)表示頂點(diǎn)v的鄰集.度為k的頂點(diǎn)稱為k-頂點(diǎn).度至少為(至多為)k的頂點(diǎn)稱為k+-頂點(diǎn)(k?-頂點(diǎn)).用di(v)表示與頂點(diǎn)v相鄰的i-頂點(diǎn)的數(shù)目.一個(gè)圖G稱為半正則的,如果它的每一條邊至少和一個(gè)最大度頂點(diǎn)相關(guān)聯(lián).否則,稱為非半正則的.一個(gè)圖G的正常邊著色是一個(gè)映射φ:E(G)→{1,···,k},使得每一對(duì)相鄰邊e1和e2,有φ(e1)(e2).用cφ(v)表示在著色φ下與v相關(guān)聯(lián)的邊所著的顏色組成的集合.一個(gè)圖G的正常邊著色φ稱為鄰點(diǎn)可區(qū)別邊著色,如果G的任何相鄰頂點(diǎn)u和v,滿足cφ(u)(v).G的鄰點(diǎn)可區(qū)別邊色數(shù)是使得G有一個(gè)k-鄰點(diǎn)可區(qū)別邊著色的最少顏色數(shù)k.

在2002年,文獻(xiàn)[1]首先討論了鄰點(diǎn)可區(qū)別邊著色問(wèn)題,并提出了以下猜想.

猜想設(shè)圖G為頂點(diǎn)數(shù)至少為3的連通圖且5,則.對(duì)于一般圖G,文獻(xiàn)[2]給出了若?(G)>1020,則.文獻(xiàn)[3]給出了.文獻(xiàn)[4]給出了.文獻(xiàn)[5]給出了若?(G)≤3,則.文獻(xiàn)[6]給出了若?(G)≤5且,則.文獻(xiàn)[7]給出了若?(G)≤4,則,和若?(G)≤5,則.本文證明了若G是一個(gè)最大度為6的非半正則圖,則.

引理1.1[7]假設(shè)G是一個(gè)?(G)≥2的半正則圖.若?(G)≡0(mod 3),則.

2 主要結(jié)果

定理2.1設(shè)G是一個(gè)最大度為6的非半正則圖,則.

證假設(shè)G是含邊數(shù)最少的連通的極小反例.由于G是非半正則的,所以存在uv∈E(G),使得dG(u)≤5且dG(v)≤5.不妨設(shè)dH(u)≤dH(v).設(shè)H=G?uv,由G的極小性可知,H有一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ,它用的顏色集C={1,2,···,12}.為了敘述起來(lái)方便,稱在φ下邊e對(duì)顏色α是允許的,若在φ下用顏色α給邊e重新著色可得H的一個(gè)新的12-鄰點(diǎn)可區(qū)別邊著色.用L(e)表示在φ下由邊e的所有允許的顏色組成的集.設(shè)xy∈E(H),且dG(x)=dG(y).若顏色β∈cφ(y)cφ(x),且|cφ(y)∩cφ(x)|=dH(x)=dH(y)?1,則稱在φ下顏色β為頂點(diǎn)x的不法顏色.用Ax表示在φ下頂點(diǎn)x的所有不法顏色組成的集.設(shè)?z(x)={cφ(y)|y∈NH(x){z}}(或?(x)={cφ(y)|y∈NH(x)}).由uv的選擇可知dH(u)+dH(v)≤8.

情形1假設(shè)dH(u)+dH(v)≤6.

情形1.1假設(shè)dH(u)=0.由uv的選擇和G的假設(shè)可知1≤dH(v)≤4.顯然,存在p∈Ccφ(v),用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形1.2假設(shè)dH(u)=1且u0∈NH(u).由uv的選擇可知1≤dH(v)≤4.

假設(shè)dH(v)=1且v0∈NH(v).若φ(vv0)6φ(uu0),顯然,存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,φ(vv0)=φ(uu0).由于|L(vv0)|≥1,所以存在q∈L(vv0).現(xiàn)用q給vv0重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而φ0(vv0)(uu0),正如前面已討論,矛盾.

假設(shè)2≤dH(v)≤4.顯然,存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形1.3假設(shè)dH(u)=2且uj∈NH(u),其中j=1,2.由uv的選擇可知2≤dH(v)≤4.

假設(shè)dH(v)=2且vj∈NH(v),其中j=1,2. 若|cφ(u)∩cφ(v)|≤1,顯然,存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,|cφ(u)∩cφ(v)|=2.不妨設(shè)φ(vv1)=1和φ(vv2)=2.在H中,若v的鄰點(diǎn)有一個(gè)5?-頂點(diǎn),不妨設(shè)dH(v1)≤5.由于|L(vv1)|≥1,所以存在p∈L(vv1).現(xiàn)用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=1,正如前面已討論,矛盾.否則,v1和v2均是6-頂點(diǎn).設(shè)v1j∈NH(v1),其中j=1,2,3,4,5.若2∈cφ(v1),因而|L(vv1)|≥1,所以存在p∈L(vv1).現(xiàn)用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=1,正如前面已討論,矛盾.否則,2(v1).不妨設(shè)φ(v1v1j)=j+2,其中j=1,2,3,4,5.若存在q∈C{cφ(v)∪cφ(v1)},用q給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=1,正如前面已討論,矛盾.否則,不妨設(shè)cφ(v11)={3,4,5,6,7,8},cφ(v12)={3,4,5,6,7,9},cφ(v13)={3,4,5,6,7,10},cφ(v14)={3,4,5,6,7,11}和cφ(v15)={3,4,5,6,7,12}. 若存在r∈{1,2},使得{r,4,5,6,7,8?v1(v11),那么用r和3分別給v1v11和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=1,正如前面已討論,矛盾.否則,在φ下,{{1,4,5,6,7,8},{2,4,5,6,7,8}}??v1(v11).由于|?v1(v11)|=5,所以存在s∈{9,10,11,12},使得{s,4,5,6,7,8?v1(v11).現(xiàn)用s和t∈{9,10,11,12}{s},分別給v1v11和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=1,正如前面已討論,矛盾.

假設(shè)3≤dH(v)≤4.由前面的討論可知,uj均是4+-頂點(diǎn),其中j=1,2.顯然,存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形1.4假設(shè)dH(u)=3.因而dH(v)=3.設(shè)vj∈NH(v),其中j=1,2,3.

假設(shè)|cφ(u)∩cφ(v)|=0.若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v),或{{p}∪cφ(u)}∈?(u).由于|L(vv1)|≥5,所以存在q∈L(vv1){cφ(v2)∪cφ(v3)}.現(xiàn)用q給vv1重新著色,用φ(vv1)給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)1≤|cφ(u)∩cφ(v)|≤2.顯然,存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|cφ(u)∩cφ(v)|=3.不妨設(shè)φ(vvj)=j,其中j=1,2,3.

在H中,假設(shè)v的鄰點(diǎn)中有一個(gè)5?-頂點(diǎn).不妨設(shè)d(v1)≤5.由情形1.3可知,v2和v3均不是3-頂點(diǎn).顯然,|L(vv1)|≥1,所以存在p∈L(vv1),用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=2,正如前面已討論,矛盾.

在H中,假設(shè)v的鄰點(diǎn)均是6-頂點(diǎn).設(shè)v1j∈NH(v1),其中j=1,2,3,4,5.

假設(shè)|{2,3}∩cφ(v1)|=0.不妨設(shè)φ(v1v1j)=j+3,其中j=1,2,3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=2,正如前面已討論,矛盾.否則,不妨設(shè)cφ(v11)={4,5,6,7,8,9},cφ(v12)={4,5,6,7,8,10},cφ(v13)={4,5,6,7,8,11}和cφ(v14)={4,5,6,7,8,12}. 若存在q∈{1,2,3},使得{q,5,6,7,8,9?v1(v11),那么先用q給v1v11重新著色.進(jìn)一步,若用4給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,從而|cφ0(u)∩cφ0(v)|=2,正如前面已討論,矛盾.否則,cφ(v15)={q,4,5,6,7,8}.現(xiàn)用10給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ00.從而|cφ00(u)∩cφ00(v)|=2,正如前面已討論,矛盾.否則,在φ下,{{1,5,6,7,8,9},{2,5,6,7,8,9},{3,5,6,7,8,9}}??v1(v11).由于|?v1(v11)|=5,所以存在r∈{10,11,12},使得{r,5,6,7,8,9?v1(v11).若用r和s∈{10,11,12}{r}分別給v1v11和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=2,正如前面已討論,矛盾.否則,cφ(v5)={r,s,5,6,7,8}.現(xiàn)用r和t∈{10,11,12}{r,s}分別給v1v11和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ00.從而|cφ00(u)∩cφ00(v)|=2,正如前面已討論,矛盾.

假設(shè)|{2,3}∩cφ(v1)|=1.不妨設(shè)φ(v1v11)=2,φ(v1v1j)=j+2,其中j=2,3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=2,正如前面已討論,矛盾.否則,不妨設(shè)cφ(v11)={2,4,5,6,7,8},cφ(v12)={2,4,5,6,7,9},cφ(v13)={2,4,5,6,7,10},cφ(v14)={2,4,5,6,7,11}和cφ(v15)={2,4,5,6,7,12}.若存在q∈{1,3},使得{q,2,5,6,7,9?v1(v12),那么用q和4分別給v1v12和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=2,正如前面已討論,矛盾.否則,在φ下,{{1,2,5,6,7,9},{2,3,5,6,7,9}}??v1(v12).由于|?v1(v12)|=5,所以存在r∈{8,10,11,12},使得{r,2,5,6,7,9?v1(v12).現(xiàn)用r和s∈{8,10,11,12}{r}分別給v1v12和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=2,正如前面已討論,矛盾.

假設(shè)|{2,3}∩cφ(v1)|=2.由于|L(vv1)|≥1,所以存在p∈L(vv1).現(xiàn)用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=2,正如前面已討論,矛盾.

情形2假設(shè)dH(u)+dH(v)=7.由uv的選擇可知dH(u)=3且dH(v)=4.設(shè)uj∈NH(u),其中j=1,2,3.由情形1可知,uj均為5+-頂點(diǎn),其中j=1,2,3.因此存在p∈C{cφ(u)∪cφ(v)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3假設(shè)dH(u)+dH(v)=8.由uv的選擇可知dH(u)=4且dH(v)=4.設(shè)vi∈NH(v),其中i=1,2,3,4.在φ下,不妨設(shè)φ(vvi)=i,其中i=1,2,3,4.設(shè)uj∈NH(u),其中j=1,2,3,4.由情形1和2可知,在H中,與u相鄰的頂點(diǎn)和與v相鄰的頂點(diǎn)均是5+-頂點(diǎn).

情形3.1假設(shè)dH(uj)=6,其中j=1,2,3,4.

情形3.1.1假設(shè)|cφ(u)∩cφ(v)|=0.設(shè)φ(uuj)=j+4,其中j=1,2,3,4.若存在p∈C{cφ(u)∪cφ(v)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v). 顯然,C{cφ(v)∪cφ(u)}={9,10,11,12}. 不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}. 若存在q∈{5,6,7,8},使得{q,2,3,4,9?v(v1),那么用q給vv1重新著色,用1給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,?v(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.現(xiàn)用10給vv1重新著色,用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.1.2假設(shè)1≤|cφ(u)∩cφ(v)|≤3.顯然,存在p∈C{cφ(u)∪cφ(v)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.1.3假設(shè)|cφ(u)∩cφ(v)|=4.

在H中,假設(shè)d6(v)=4.因此d(vi)=6,其中i=1,2,3,4.設(shè)v1j∈NH(v1){v},其中j=1,2,3,4,5.

假設(shè)|{2,3,4}∩cφ(v1)|=0.不妨設(shè)φ(v1v1j)=j+4,其中j=1,2,3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,不妨設(shè)cφ(v11)={5,6,7,8,9,10},cφ(v12)={5,6,7,8,9,11}和cφ(v13)={5,6,7,8,9,12}.若存在q∈{1,2,3,4},使得{q,6,7,8,9,10}/∈?v1(v11),那么先用q給v1v11重新著色.進(jìn)一步,若用5給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,cφ(v14)={q,5,6,7,8,9},或cφ(v15)={q,5,6,7,8,9}. 不妨設(shè)cφ(v14)={q,5,6,7,8,9}. 若用11給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ00,從而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否則,cφ(v15)={q,6,7,8,9,11}.現(xiàn)用12給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ000.從而|cφ000(u)∩cφ000(v)|=3,正如情形3.1.2,矛盾.否則,在φ下,{{1,6,7,8,9,10},{2,6,7,8,9,10},{3,6,7,8,9,10},{4,6,7,8,9,10}}??v1(v11).類似的,{{1,5,7,8,9,11},{2,5,7,8,9,11},{3,5,7,8,9,11},{4,5,7,8,9,11}}??v1(v12).由于|?v1(v1j)|=5,其中j=1,2,所以存在r∈{11,12},不妨設(shè)r=11,使得{6,7,8,9,10,11}/∈?v1(v11),存在s∈{10,12},使得{s,5,7,8,9,11?v1(v12).若用11和12分別給v1v11和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,cφ(v14)={6,7,8,9,11,12},或cφ(v15)={6,7,8,9,11,12}.不妨設(shè)cφ(v14)={6,7,8,9,11,12}.若用s和t∈{10,12}{s}分別給v1v12和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ00,從而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否則,cφ(v15)={5,7,8,9,10,12}.現(xiàn)用11,s和t分別給v1v11,v1v12和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ000.從而|cφ000(u)∩cφ000(v)|=3,正如情形3.1.2,矛盾.

假設(shè)|{2,3,4}∩cφ(v1)|=1.不妨設(shè)φ(v1v11)=2和φ(v1v1j)=j+3,其中j=2,3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾. 否則,不妨設(shè)cφ(v11)={2,5,6,7,8,9},cφ(v12)={2,5,6,7,8,10},cφ(v13)={2,5,6,7,8,11}和cφ(v14)={2,5,6,7,8,12}. 若存在q∈{1,3,4},使得{q,2,6,7,8,10?v1(v12),那么先用q給v1v12重新著色.進(jìn)一步,若用5給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,cφ(v15)={q,2,5,6,7,8}.現(xiàn)用11給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ00.從而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.否則,在φ下,{{1,2,6,7,8,10},{2,3,6,7,8,10},{2,4,6,7,8,10}}??v1(v12).由于|?v1(v12)|=5,所以存在r∈{9,11,12},使得{r,2,6,7,8,10?v1(v12),那么先用r給v1v12重新著色.進(jìn)一步,若用s∈{9,11,12}{r}給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾. 否則,cφ(v15)={r,s,2,6,7,8}. 現(xiàn)用t∈{9,11,12}{r,s}給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ00.從而|cφ00(u)∩cφ00(v)|=3,正如情形3.1.2,矛盾.

假設(shè)|{2,3,4}∩cφ(v1)|=2.不妨設(shè)φ(v1v11)=2,φ(v1v12)=3和φ(v1v1j)=j+2,其中j=3,4,5.若存在p∈C{cφ(v)∪cφ(v1)},用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,不妨設(shè)cφ(v11)={2,3,5,6,7,8},cφ(v12)={2,3,5,6,7,9},cφ(v13)={2,3,5,6,7,10},cφ(v14)={2,3,5,6,7,11}和cφ(v15)={2,3,5,6,7,12}.若存在q∈{1,4},使得{q,2,3,6,7,10}/∈?v1(v13),那么用q和5分別給v1v13和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,在φ下,{{1,2,3,6,7,10},{2,3,4,6,7,10}}??v1(v13).由于|?v1(v13)|=5,所以存在r∈{8,9,11,12},使得{r,2,3,6,7,10?v1(v13).現(xiàn)用r和s∈{8,9,11,12}{r}分別給v1v13和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.

假設(shè)|{2,3,4}∩cφ(v1)|=3.由于|L(vv1)|≥1,所以存在p∈L(vv1).現(xiàn)用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.

在H中,假設(shè)d6(v)≤3.不妨設(shè)d(v1)=5.若|{2,3,4}∩cφ(v1)|≥1,因而|L(vv1)|≥1,所以存在p∈L(vv1).現(xiàn)用p給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,|{2,3,4}∩cφ(v1)|=0.不妨設(shè)φ(v1v1j)=j+4,其中j=1,2,3,4.若存在q∈C{cφ(v)∪cφ(v1)},用q給vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,不妨設(shè)cφ(v11)={5,6,7,8,9},cφ(v12)={5,6,7,8,10},cφ(v13)={5,6,7,8,11}和cφ(v14)={5,6,7,8,12}. 若存在r∈{1,2,3,4},使得{r,6,7,8,9?v1(v11),那么用r和5分別給v1v11和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.否則,在φ下,?v1(v11)={{1,6,7,8,9},{2,6,7,8,9},{3,6,7,8,9},{4,6,7,8,9}}.現(xiàn)用10和11分別給v1v11和vv1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=3,正如情形3.1.2,矛盾.

情形3.2假設(shè)dH(u1)=5,且d(uj)=6,其中j=2,3,4.

情形3.2.1假設(shè)|cφ(u)∩cφ(v)|=0.

不妨設(shè)φ(uuj)=j+4,j=1,2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v),或{{p}∪cφ(u)}∈?(u).顯然,C{cφ(v)∪cφ(u)}={9,10,11,12}.

假設(shè)|Av∩{9,10,11,12}|=4. 不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9?v(v1),那么先用q給vv1重新著色.進(jìn)一步,若用1給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u1)={1,5,6,7,8}.現(xiàn)用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,?v(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.先用10給vv1重新著色.進(jìn)一步,若用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u1)={5,6,7,8,11}.現(xiàn)用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|=1. 不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q給uu1重新著色,用5給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(v4)={1,2,3,4,5}.由于|?v(v1)|=4,所以存在r∈{5,6,7,8,12},使得{r,2,3,4,9?v(v1).現(xiàn)用r給vv1重新著色,用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.2.2假設(shè)|cφ(u)∩cφ(v)|=1. 不妨設(shè)φ(uu1)=1和φ(uuj)=j+3,其中j=2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v)或{{p}∪cφ(u)}∈?(u).顯然,C{cφ(v)∪cφ(u)}={8,9,10,11,12}. 不妨設(shè)cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}. 若存在q∈{5,6,7,12},使得{q,1,3,4,9?v(v2),那么用q給vv2重新著色,用2給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,?v(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.現(xiàn)用10給vv2重新著色,用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.2.3假設(shè)2≤|cφ(u)∩cφ(v)|≤3.顯然,存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.2.4假設(shè)|cφ(u)∩cφ(v)|=4.設(shè)φ(uuj)=j,其中j=1,2,3,4.

假設(shè)|{2,3,4}∩cφ(u1)|≥1.由于|L(uu1)|≥1,所以存在p∈L(uu1).現(xiàn)用p給uu1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.假設(shè)|{2,3,4}∩cφ(u1)|=0.設(shè)u1j∈NH(u1){u},其中j=1,2,3,4.不妨設(shè)φ(u1u1j)=j+4,其中j=1,2,3,4.若存在q∈C{cφ(u)∪cφ(u1)},用q給uu1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0,從而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.否則,不妨設(shè)cφ(u11)={5,6,7,8,9},cφ(u12)={5,6,7,8,10},cφ(u13)={5,6,7,8,11}和cφ(u14)={5,6,7,8,12}.若存在r∈{1,2,3,4},使得{r,6,7,8,9?u1(u11),那么用r和5分別給u1u11和uu1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.否則,在φ下,?u1(u11)={{1,6,7,8,9},{2,6,7,8,9},{3,6,7,8,9},{4,6,7,8,9}}.現(xiàn)用10和11分別給u1u11和uu1重新著色可得H的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色φ0.從而|cφ0(u)∩cφ0(v)|=3,正如情形3.2.3,矛盾.

情形3.3假設(shè)dH(u1)=dH(u2)=5且dH(u3)=dH(u4)=6.

情形3.3.1假設(shè)|cφ(u)∩cφ(v)|=0.不妨設(shè)φ(uuj)=j+4,j=1,2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v),或{{p}∪cφ(u)}∈?(u).顯然,C{cφ(v)∪cφ(u)}={9,10,11,12}.

假設(shè)|Av∩{9,10,11,12}|=4. 不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9}/∈?v(v1),那么先用q給vv1重新著色.進(jìn)一步,若用1給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}.不妨設(shè)cφ(u1)={1,5,6,7,8}.若用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={5,6,7,8,10}.現(xiàn)用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,?v(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.類似的,?v(v2)={{1,3,4,5,10},{1,3,4,6,10},{1,3,4,7,10},{1,3,4,8,10}}.先用10和11分別給vv1和vv2重新著色.進(jìn)一步,若用2給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u1)={2,5,6,7,8}或cφ(u2)={2,5,6,7,8}. 不妨設(shè)cφ(u1)={2,5,6,7,8}. 若用 9給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={5,6,7,8,9}.現(xiàn)用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|≥1. 不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q給uu1重新著色,用5給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={q,5,6,7,8}或cφ(v4)={1,2,3,4,5}.若cφ(v4)={1,2,3,4,5},顯然,存在r∈{5,6,7,8,12},使得{r,2,3,4,9?v(v1),那么先用r給vv1重新著色.進(jìn)一步,若用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={5,6,7,8,10}.現(xiàn)用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.若cφ(u2)={q,5,6,7,8},由于|L(uu2)|≥3,所以存在s∈L(uu2)cφ(u1).現(xiàn)用s給uu2重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{9,10,11,12}|=2. 因而|Au∩{9,10,11,12}|=2. 不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(u1)={5,6,7,8,11}和c(u2)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).現(xiàn)用q給uu1重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.3.2假設(shè)|cφ(u)∩cφ(v)|=1.

不妨設(shè)φ(uu1)=1和φ(uuj)=j+3,其中j=2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v),或{{p}∪cφ(u)}∈?(u).顯然,C{cφ(v)∪cφ(u)}={8,9,10,11,12}.

假設(shè)|Av∩{8,9,10,11,12}|=4.因而|Au∩{8,9,10,11,12}|≥1.不妨設(shè)cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}.若存在q∈{5,6,7,12},使得{q,1,3,4,9?v(v2),那么先用q給vv2重新著色.進(jìn)一步,若用2給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={1,2,5,6,7}.現(xiàn)用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,?v(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.先用10給vv2重新著色.進(jìn)一步,若用8給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={1,5,6,7,8}.現(xiàn)用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{8,9,10,11,12}|=3.因而|Au∩{8,9,10,11,12}|=2.不妨設(shè)cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(u1)={1,5,6,7,11}和cφ(u2)={1,5,6,7,12}.由于|L(uu2)|≥3,所以存在q∈L(uu2)cφ(u1).現(xiàn)用q給uu2重新著色,用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.3.3假設(shè)|cφ(u)∩cφ(v)|=2.

不妨設(shè)φ(uu1)=1,φ(uu2)=2,φ(uu3)=5 和φ(uu4)=6. 若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v)或{{p}∪cφ(u)}∈?(u).顯然,C{cφ(v)∪cφ(u)}={7,8,9,10,11,12}.不妨設(shè)cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(v4)={1,2,3,4,10},cφ(u1)={1,2,5,6,11}和cφ(u2)={1,2,5,6,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).現(xiàn)用q給uu1重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.3.4假設(shè)|cφ(u)∩cφ(v)|=3.顯然,存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.3.5假設(shè)|cφ(u)∩cφ(v)|=4.與情形3.2.4類似,矛盾.

情形3.4假設(shè)d(uj)=5,其中j=1,2,3,且d(u4)=6.

情形3.4.1假設(shè)|cφ(u)∩cφ(v)|=0.

不妨設(shè)φ(uuj)=j+4,j=1,2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v)或{{p}∪cφ(u)}∈?(u).顯然,C{cφ(v)∪cφ(u)}={9,10,11,12}.

假設(shè)|Av∩{9,10,11,12}|=4. 不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(v4)={1,2,3,4,12}.若存在q∈{5,6,7,8},使得{q,2,3,4,9?v(v1),那么先用q給vv1重新著色.進(jìn)一步,若用1給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}或cφ(u3)={1,5,6,7,8}.不妨設(shè)cφ(u1)={1,5,6,7,8}.若用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={5,6,7,8,10}或cφ(u3)={5,6,7,8,10}.不妨設(shè)cφ(u2)={5,6,7,8,10}.若用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={5,6,7,8,11}.現(xiàn)用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,?v(v1)={{2,3,4,5,9},{2,3,4,6,9},{2,3,4,7,9},{2,3,4,8,9}}.類似的,?v(v2)={{1,3,4,5,10},{1,3,4,6,10},{1,3,4,7,10},{1,3,4,8,10}},?v(v3)={{1,2,4,5,11},{1,2,4,6,11},{1,2,4,7,11},{1,2,4,8,11}}和?v(v4)={{1,2,3,5,12},{1,2,3,6,12},{1,2,3,7,12},{1,2,3,8,12}}.先用10,11,12和9分別給vv1,vv2,vv3和vv4重新著色.進(jìn)一步,若用1給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u1)={1,5,6,7,8}或cφ(u2)={1,5,6,7,8}或cφ(u3)={1,5,6,7,8}. 不妨設(shè)cφ(u1)={1,5,6,7,8}.若用2給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={2,5,6,7,8}或cφ(u3)={2,5,6,7,8}. 不妨設(shè)cφ(u2)={2,5,6,7,8}. 若用 3給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={3,5,6,7,8}.現(xiàn)用4給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{9,10,11,12}|=3. 因而|Au∩{9,10,11,12}|≥1. 不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(v3)={1,2,3,4,11}和cφ(u1)={5,6,7,8,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1).若用q給uu1重新著色,用5給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={q,5,6,7,8}或cφ(u3)={q,5,6,7,8}或cφ(v4)={1,2,3,4,5}. 若cφ(v4)={1,2,3,4,5},顯然,存在r∈{5,6,7,8,12},使得{r,2,3,4,9?v(v1),那么先用r給vv1重新著色.進(jìn)一步,若用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={5,6,7,8,10}或cφ(u3)={5,6,7,8,10}.不妨設(shè)cφ(u2)={5,6,7,8,10}.若用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={5,6,7,8,11}.顯然存在s∈{6,7}{r},不妨設(shè)s=7.由于|L(uu3)|≥3,所以存在t∈L(uu3){cφ(u1)∪cφ(u2)}.現(xiàn)用t給uu3重新著色,用7給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.若cφ(u2)={q,5,6,7,8}或cφ(u3)={q,5,6,7,8},不妨設(shè)cφ(u2)={q,5,6,7,8}.由于|L(uu2)|≥3,所以存在r∈L(uu2)cφ(u1).若用r給uu2重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={r,5,7,8,12}.由于|L(uu3)|≥2,所以存在s∈L(uu3).顯然,(u1),6(u3)和12(u2).因而用s給uu3重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{9,10,11,12}|=2.因而|Au∩{9,10,11,12}|≥2.不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(v2)={1,2,3,4,10},cφ(u1)={5,6,7,8,11}和cφ(u2)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).若用q給uu1重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={q,6,7,8,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2){cφ(u1)∪cφ(u3)}.現(xiàn)用r給uu2重新著色,用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{9,10,11,12}|=1.因而|Au∩{9,10,11,12}|=3.不妨設(shè)cφ(v1)={1,2,3,4,9},cφ(u1)={5,6,7,8,10},cφ(u2)={5,6,7,8,11}和cφ(u3)={5,6,7,8,12}. 由于|L(uu1)|≥3,所以存在q∈L(uu1){cφ(u2)∪cφ(u3)}.現(xiàn)用q給uu1重新著色,用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.4.2假設(shè)|cφ(u)∩cφ(v)|=1.

不妨設(shè)φ(uu1)=1,φ(uuj)=j+3,j=2,3,4.若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v)或{{p}∪cφ(u)}∈?(u).顯然,C{cφ(v)∪cφ(u)}={8,9,10,11,12}.

假設(shè)|Av∩{8,9,10,11,12}|=4.因而|Au∩{8,9,10,11,12}|≥1.不妨設(shè)cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(v4)={1,2,3,4,11}和cφ(u1)={1,5,6,7,12}.若存在q∈{5,6,7,12},使得{q,1,3,4,9?v(v2),那么先用q給vv2重新著色.進(jìn)一步,若用2給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾. 否則,cφ(u2)={1,2,5,6,7}或cφ(u3)={1,2,5,6,7}. 不妨設(shè)cφ(u2)={1,2,5,6,7}.若用8給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={1,5,6,7,8}.現(xiàn)用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,?v(v2)={{1,3,4,5,9},{1,3,4,6,9},{1,3,4,7,9},{1,3,4,9,12}}.類似的,?v(v3)={{1,2,4,5,10},{1,2,4,6,10},{1,2,4,7,10},{1,2,4,10,12}}和 ?v(v4)={{1,2,3,5,11},{1,2,3,6,11},{1,2,3,7,11},{1,2,3,11,12}}.先用10,11和9分別給vv2,vv3和vv4重新著色.進(jìn)一步,若用2給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u2)={1,2,5,6,7}或cφ(u3)={1,2,5,6,7}. 不妨設(shè)cφ(u2)={1,2,5,6,7}.若用 3給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={1,3,5,6,7}.現(xiàn)用4給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{8,9,10,11,12}|=3.因而|Au∩{8,9,10,11,12}|≥2.不妨設(shè)cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(v3)={1,2,3,4,10},cφ(u1)={1,5,6,7,11}和cφ(u2)={1,5,6,7,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).若用q給uu1重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={q,5,6,7,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2){cφ(u1)∪cφ(u3)}.現(xiàn)用r給uu2重新著色,用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{8,9,10,11,12}|=2.因而|Au∩{8,9,10,11,12}|=3.不妨設(shè)cφ(v1)={1,2,3,4,8},cφ(v2)={1,2,3,4,9},cφ(u1)={1,5,6,7,10},cφ(u2)={1,5,6,7,11}和cφ(u3)={1,5,6,7,12}. 由于|L(uu2)|≥3,所以存在q∈L(uu2){cφ(u1)∪cφ(u3)}. 現(xiàn)用q給uu2重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.4.3假設(shè)|cφ(u)∩cφ(v)|=2.

不妨設(shè)φ(uu1)=1,φ(uu2)=2,φ(uu3)=5 和φ(uu4)=6. 若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v)或{{p}∪cφ(u)}∈?(u).顯然,C{cφ(v)∪cφ(u)}={7,8,9,10,11,12}.

假設(shè)|Av∩{7,8,9,10,11,12}|=4.因而|Au∩{7,8,9,10,11,12}|≥2.不妨設(shè)cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(v4)={1,2,3,4,10},cφ(u1)={1,2,5,6,11}和cφ(u2)={1,2,5,6,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1)cφ(u2).若用q給uu1重新著色,用12給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,cφ(u3)={q,2,5,6,12}.由于|L(uu2)|≥3,所以存在r∈L(uu2){cφ(u1)∪cφ(u3)}.現(xiàn)用r給uu2重新著色,用11給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

假設(shè)|Av∩{7,8,9,10,11,12}|=3.因而|Au∩{7,8,9,10,11,12}|=3.不妨設(shè)cφ(v1)={1,2,3,4,7},cφ(v2)={1,2,3,4,8},cφ(v3)={1,2,3,4,9},cφ(u1)={1,2,5,6,10},cφ(u2)={1,2,5,6,11}和cφ(u3)={1,2,5,6,12}.由于|L(uu3)|≥3,所以存在q∈L(uu3){cφ(u1)∪cφ(u2)}.現(xiàn)用q給uu3重新著色,用10給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.4.4假設(shè)|cφ(u)∩cφ(v)|=3.

不妨設(shè)φ(uuj)=j,其中j=1,2,3.設(shè)φ(uu4)=5.若存在p∈C{cφ(v)∪cφ(u)},用p給uv著色可得G的一個(gè)12-鄰點(diǎn)可區(qū)別邊著色,矛盾.否則,在φ下,{{p}∪cφ(v)}∈?(v)或{{p}∪cφ(u)}∈?(u). 顯然,C{cφ(v)∪cφ(u)}={6,7,8,9,10,11,12}. 不妨設(shè)cφ(v1)={1,2,3,4,6},cφ(v2)={1,2,3,4,7},cφ(v3)={1,2,3,4,8},cφ(v4)={1,2,3,4,9},cφ(u1)={1,2,3,5,10},cφ(u2)={1,2,3,5,11}和cφ(u3)={1,2,3,5,12}.由于|L(uu1)|≥3,所以存在q∈L(uu1){cφ(u2)∪cφ(u3)}.現(xiàn)用q給uu1重新著色,用11給uv著色可得G的一個(gè)12鄰點(diǎn)可區(qū)別邊著色,矛盾.

情形3.4.5假設(shè)|cφ(u)∩cφ(v)|=4.與情形3.2.4類似,矛盾.

情形3.5假設(shè)d(uj)=5,其中j=1,2,3,4.由于G是最大度為6的連通圖,所以在G中存在一個(gè)6-頂點(diǎn)w,和一條最短路p=w0,w1,···,wt,其中w0=u,wt=w.設(shè)ws是這條路上的第一個(gè)6-頂點(diǎn).根據(jù)情形1,2和3.1–3.4可知d(wk)=5且s≥3,其中k=0,1,···,s?1.因此找到了一個(gè)5-頂點(diǎn)ws?1和一個(gè)6-頂點(diǎn)ws相鄰.令H=G?ws?2ws?1.正如前面已討論,矛盾.因此這個(gè)定理成立.

推論2.1設(shè)G是一個(gè)最大度為6的圖,則.

證由引理1.1和定理2.1可得.