張東翰

(商洛學院 數學與計算機應用學院，陜西 商洛 726000)

1 主要定義和引理

圖G的一條邊e稱為被剖分，是指刪除其并加上連接其2個端點的一條長為2的路.

2 主要結果

f(v0vi)=i(i=1,2,3),f(v1u1)=3,f(v2u2)=1,f(v3u3)=2,f(u1v2)=f(u2v3)=f(u3v1)=4，

證畢.

情形1v1u1染顏色2

u1v2只能從集合{1,3,4}中選擇顏色.當u1v2染顏色1時，那么v0v1u1v2v0是一個2-色圈，矛盾.當u1v2染顏色3時， 那么v1u1v2v0v3是一個2-色路，矛盾.當u1v2染顏色4時，那么v1u1v2v0v4是一個2-色路，矛盾.因此,v1u1不能染顏色2.

情形2v1u1染顏色3

u1v2只能從集合{1,4}中選擇顏色.當u1v2染顏色1時，那么v2u1v1v0v3是一個2-色路，矛盾.當u1v2染顏色4時，v2u2只能從集合{1,3}中選擇顏色，分v2u2染顏色3和v2u2染顏色1兩種情況討論.

情形1)v2u2染顏色3

u2v3只能從集合{1,2,4}中選擇顏色.當u2v3染顏色1時，那么v1v0v3u2v2是一個2-色路，矛盾.當u2v3染顏色2時，那么v2u2v3v0v2是一個2-色圈，矛盾.當u2v3染顏色4時，那么v2u2v3v0v4是一個2-色路，矛盾.

情形2)v2u2染顏色1

為了保證星邊染色的條件，很容易看出u2v3只能染顏色4，v3u3只能染顏色2，u3v4只能染顏色1,v4u4只能從集合{2,3}中選擇顏色.當v4u4染顏色2時，那么u4v4v0v2u1是一個2-色路，矛盾.當u4v1染顏色3時，那么u4v4v0v3u2是一個2-色路，矛盾.

因此，v1u1不能染顏色3.

情形3v1u1染顏色4

此時可以用情形2相同的分析方法而得出矛盾.

f(v0vi)=i(i=1,2,3,4),f(v1u1)=f(u2v3)=4,f(u4v1)=f(u1v2)=3,

f(v3u3)=f(v4u4)=5,f(v2u2)=1,f(u3v4)=2,

證畢.

f(v0vi)=i(i=1,2,3,4,5),f(v1u1)=f(v4u4)=3,f(u1v2)=f(u5v1)=4,

f(v2u2)=f(u4v5)=1,f(u2v3)=f(u3v4)=5,f(v3u3)=f(v5u5)=2,

證畢.

證明根據引理2～4，可知當時3≤n≤5，結論成立. 下面證明當n≥6時，結論也成立.

f(v0vi)=i(i=1,…,n),f(v1u1)=3,f(u1v2)=4,
f(v2u2)=1,f(u2v3)=5,f(v3u3)=2,f(u3v4)=5,

綜上所述，定理1成立.

證畢.