關于極大外平面圖的度偏差的極值

(湖南師范大學 數學與統計學院，長沙，410081)

1 引言

本文僅考慮簡單、無向、連通和有限的圖G,分別有邊集E(G)和頂點集V(G).以G-{vi}(1≤i≤n)表示從G中去掉頂點vi后得到的子圖，dG(vi)表示G中vi的度(可簡寫為d(vi))，nj(1≤j≤n-1)表示圖G中度為j的頂點個數，N(v)表示頂點v的鄰點集，Pn表示有n個頂點的路，G1和G2的聯圖G1∨G2表示G1和G2中各頂點互相連接后所得到的圖，符號[a]表示對a取小于等于a的最大整數.在文獻[1]中提到，若平面圖G的所有點都在外部區域上，則稱此平面圖G是外平面圖;若外平面圖G不能再加上邊而不失去外平面性，則稱此外平面圖G為極大外平面圖.我們把外部區域的邊界稱為界環.顯然界環是一個圈，用Cn=(v1,v2,…,vn)來表示，圈Cn上的點下標連續且v1與vn相鄰.易見，極大外平面圖有2n-3條邊(n≥3).沒有提到的定義、術語請參見文獻[1].

2 預備知識

圖

當n=3,4,5時，只有一個非同構的極大外平面圖，當n=6時，有三個非同構的極大外平面圖, 具體見圖2.

圖2 n≤6的極大外平面圖

下面先介紹極大外平面圖的有關性質.

引理2[1]設G是有n個頂點的外平面圖(n≥3),那么G為極大外平面圖的充要條件是在G的邊界Cn內的所有區域均為三角形.

引理4[10]設G是有n個頂點的極大外平面圖(n>3),則G的任意兩個二度頂點不能相鄰.當n=3時，極大外平面圖是一個三角形，此時三個頂點彼此相鄰且度為2.

由極大外平面圖的定義我們易得下面結論.

引理5設G是有n個頂點的極大外平面圖(n≥3),則圖G界環上的每條邊只能存在于一個三角形中.

引理6設G是有n個頂點的極大外平面圖(n≥3),且n2=2,則有n3≥2.

證明由極大外平面圖的定義，由G的邊界上四個下標連續的頂點導出的子圖只有圖3中的a,b,c三種情況.下面對該三種情況分別進行討論.

圖3 極大外平面圖G的邊界的四個下標連續的頂點的3種導出子圖

(i)當G中存在邊界的四個下標連續的頂點的導出子圖a時,設v1左邊邊界上的鄰點為vn,由引理2可知，v3必與除v1,v2,v4的頂點外至少還有一個鄰點：

若v3與vn不相鄰，則v3必與vx∈VG{v1,v2,v3,v4,vn}相鄰.故可把G分為①，②，③三個部分，如圖4所示.顯然，這三個部分都是極大外平面圖.由引理4可知，在①中必有一個除v1,v3,vx外的2度頂點(因為v3與vn不相鄰，所以v1在①中不是2度頂點)，在③中必有一個除v3,vx外的2度頂點.又d(v2)=2,所以在G中就至少存在三個二度頂點，這樣就與G中n2=2矛盾了.

若v3與vn相鄰，則vn,v1,v2,v3的導出子圖為情況b，此時d(v2)=2,d(v1)=3.再考慮v4的度的情況.當v3與v5相鄰時，如圖5所示，d(v4)=2.令G′=G-{v2,v4},則G′也是極大外平面圖.在G′中，因為v3與vn相連，所以dG′(v1)=2.再根據引理4，若在G′中v5不是2度頂點，則除v1,v3,v5外G′至少還有一個2度頂點，故G中至少有三個二度頂點，與n2=2矛盾.所以v1,v5必是G′中的2度頂點，此時v3與vn,v3與v6相鄰，d(v1)=d(v5)=3.當v3與v5不相鄰時，d(v4)≥3.綜上所述，當只有一個頂點的度為2時，至少伴隨一個3度頂點；當有兩個頂點的度為2時，至少伴隨兩個3度頂點.

(ii)當G中存在邊界的四個下標連續的頂點的導出子圖b時，根據引理2，必有d(v2)=2,d(v3)=3,d(v4)≥3,所以一個2度頂點必定至少伴隨一個3度頂點.

(iii)當G中存在邊界四個下標連續的頂點的導出子圖c時，由極大外平面圖定義可知，d(v2)≥3,d(v3)≥3.接下來考慮v1,v4的度.當d(v1)=2，即v2與vn相鄰時，若v3與vn相鄰，則vn,v1,v2,v3的導出子圖為圖3中情況b；若v3與vn不相鄰，則vn,v1,v2,v3的導出子圖為圖3中情況a.同理，當d(v4)=2時，有同樣的結果.故存在一個2度頂點必定伴隨一個3度頂點.

綜上分析，當n2=2時，n3≥2得證.

3 主要結論

證明顯然當n=7時，有4個不同構的極大外平面圖(如圖6).

圖6 4個不同構的7階極大外平面圖

近年來，通過與北京、上海、山東、吉林、湖北、湖南、廣西、貴州、內蒙古等省、自治區、直轄市的數十個區縣黨委統戰部門的交流，結合重慶基層統戰工作的現狀，發現盡管基層統戰工作在某些方面存在的問題有重慶的個性，但就其他方面的問題來說，全國各地不同程度地存在同樣的問題。新時代基層統戰工作創新發展的制約因素主要包括如下：

令

由引理1知，d(u)+d(w)≥7,故有下面的結論：

定理2若G是一個n≥6的極大外平面圖，則

所以s(G)的值只與n2,n3有關.

又因為G中必定存在2度頂點，所以我們首先確定一個2度頂點v2，再分析v3,v4的度的大小.