t h el i n e a r a r b o r i c i t ya n d the l i n e a r 2 - a r b o r i c i t yo fgraphs abstractint h i sthesi8，we studyt h e1ineara r b o r i c i t ya n 2 一 a r b o r i c i t yo fg r a p h s l e tf 口( g ) ，f a 2 ( g ) ，盯l d ( g ) d e n o t et h e1 i n e 8 r8 r b o r i c i t y it h el i n e a r2 盯莖s g ! 二! 中 壤l 互；矗i 善i 耋晷荸苧妻毒；墨雩i 一千掃籠霎? 量囊矗l 副l 耋竄氅垂薹i l 一輦鼻i i h 蓮! ；妻_ 葶蓬三釘世! 疆二弼 x 一、緒論 ( 一) 、基本概念 在本節(jié)中，我們定義一些本文要用到的圖論的基本術(shù)語與符號我們用l s i 表示集合s 中的元素個數(shù)用f 0 1 ，1 0 1 分別表示不小于$ 的最小整數(shù)和不大于z 的最大整數(shù) 一個尤向圖是一個有序?qū) = ( k e ) ，其中礦是一個有限集合，e 是y 中的 _ i 同冗素的無序?qū)Φ募蟳 中的元素叫做圖g 的頂點，e 中的元素叫做圖g 的邊我們通常用y ( g ) ，e ( g ) 分別表示圖g 的頂點集合和邊集合沒有重邊和 環(huán)的圖叫做簡單圖除非特別指出，本文研究的圖均指有限簡單無向圖通常稱 含有n 個頂點的圖為n 階圖對于圖g 中的頂點u 和 ，若邊e = 伽e ( g ) ，則 稱u 和u 相鄰，和 互為鄰點；稱u 和 是e 的端點，u 和 分別與e 關(guān)聯(lián)若g 的邊e 和，有一個公共端點，則稱e 和，相鄰在圖g 中與頂點札相鄰的頂點的 全體叫作u 的鄰域，記作( 讓) 稱l | g ( u ) i 為頂點的度數(shù)，記作d g ( 釷) 稱度數(shù) 為的頂點為一點g 中頂點的度中最大者和最小者分別稱為g 的最大度和最 小度，分別記作( g ) 和6 ( g ) 度數(shù)為o 的頂點稱為孤立點，度數(shù)為1 的頂點稱 為懸掛點( 葉子) ，與懸掛點相關(guān)聯(lián)的邊稱為懸掛邊在不產(chǎn)生混淆的情況下，我 們把i y ( g ) 1 ，l e ( g ) i ，b ( ) ，d g ( u ) ，( g ) ，6 ( g ) 分別簡記為l y i ，i 曰“j v ( 讓) ，d ( 亂) ，d 對于圖g = ( v e ) 和圖日= ( y 7 ，) ，若有y v e e ，則稱圖h 是圖g 的一個予圖對ry y ( g ) ，我們把圖g 中屬于y 的頂點以及與y 中的點關(guān) 聯(lián)的邊都刪除所得到的圖記作g 或g 一對于 ，口y ( g ) ，伽譬f ( g ) ，我 們把在圖g 中連接頂點u ， 所得到的圖記作g + 伽) 對于y ( g ) ，我們把 i = | ! y 作為頂點集，e = eie = u p e ( g ) ，u ， y ) 作為邊集的圖叫做g 中由 頂點子集y 導(dǎo)出的子圖，記作g 【y 】設(shè)g l = ( k ，置) ，g 2 = ( ，易) 是兩個圖，稱 圖g = ( uy 2 ，e lue 2 ) 為圖g l 和圖g 2 的并，記作g u 日 圖g 的一條途徑是一個有限非空的點邊交替序列叫= 咖8 l ”l 印e k 饑，使得 對l t ，e t = 饑一l 叫若途徑掣上的頂點，”l ，噸，互不相同，則稱 為 一條路，記作r 稱如，分別為路r 的起點和終點稱起點和終點相同的路 為圈稱路( 圈) 上的邊數(shù)為路( 圈) 的長度，常用只，q 表示點數(shù)為的路和圈 稱圖g 中最短圈的長度為g 的圍長，記作9 ( g ) 圖g 中兩頂點u 和 的距離是 指g 中從u 到 的最短路的路長，記作如( u ，口) ，簡記為d ( u ， ) 任何兩個頂點間 都有一條路連接的圖稱為連通圖，否則稱為不連通豳一個圖g 的極大連通分 支稱為g 的分支連通圖的連通分支是1 ，記g ，的分支個數(shù)為u ( g ) 對于頂點 y ( g ) ，若滿足u ( g 一”) u ( g ) ，則稱 是g 的割點稱圖g 中不含割點的極 大連通分支為g 的塊若g 連通且不含圈，則稱此圖為一棵樹，常用死表示頂 點數(shù)為n 的一棵樹對于連通圖g = ( k e ) ，y y 使得g 一不連通，則稱 是g 的點割集若i i = ，則稱為舡點割集對于g ，稱圖g 中頂點數(shù) 最少的點割集的點數(shù)為圖g 的連通度，記作k ( g ) 定義的連通度為禮一1 ，不 連通圖的連通度為0 若g 滿足k ( g ) 2 ，則稱g 是“連通的 如果能將圖g 畫在平面上使得它的邊僅在端點處才可能相交，則稱圖g 是可平面圖圖的這種平面上的畫法稱為圖的平面嵌入，或稱為平面圖設(shè)圖g 是平面圖，我們常用f ( g ) 表示面集合對于，f ( g ) ，用6 ( ，) 表示組成面，的 閉途徑若1 ，u 2 ，u 。是6 ( ，) 上按順時針排列的點，我們就記，= l t 2 】 稱點u l ，u 2 ，u 。與面，相鄰把途徑6 ( ，) 的長度稱為面，的度 圖g 的一個正常b 著色是一個映射：y ( g ) 一 1 ，2 ，) ，使得對地 e ( g ) ，有廬( t ) 妒( 口) 定義圖g 的色數(shù)為x ( g ) = i r 垃n k i g 有一個正常b 著色) 若g 有一個正常一著色，則稱g 是b 可著色的本文中除非特別申明，圖g 的 七著色均指正常舡著色 如果圖g 的所有頂點的度都是d ，則稱g 是辦正則的禮階的0 正則圖g 稱為空圖，記為0 。禮階的m 一1 ) 正則圖就是完全圖，記為倘若y ( g ) 能夠 被劃分為互不相交的子集合u ，k ，磙，使得g 的任何邊的兩個端點都不在同 一個k 中，則稱g 為b 部圖如果對1 j 曼，中的每一個點與k 中的 所有點相鄰，則稱g 為完全肛部圖若i k i = 啦，t l ，2 ，七，則記此完全一部 圖為玩：，m i 若口1 = 口2 一= = m ，則記m 。= 砩2 一部圖有時也叫 二分圖 圖g 中兩兩不相鄰的點子集稱為g 的點獨立集最大的點獨立集中頂點的 數(shù)目稱為圖的點獨立數(shù)，記為a ( g ) 圖g 中兩兩不相鄰的邊子集稱為g 的邊獨 2 立集，也叫對集：攝大的邊獨立集中邊的數(shù)目稱為圖的邊獨立數(shù)，記為o ，( g ) 圖 g 的正則支撐子圖稱為g 的一個融因子如果圖g 可以分解為互不相交的 因子之并，則稱g 可融因予分解如果圖g 有一個筘因子分解且每個2 一因 子是h a m i l t o n 圈，則稱此因子分解為h a m i l t o n 分解 設(shè)p 是一些連通圖的集合我們假設(shè)p 具有封閉性，即若日p ，則日的任 何連通了- 圖也屬于p 一個圖g 的( p i ) 染色是指用種顏色對y ( g ) 進行染 色。并使得染同一種顏色的點集的導(dǎo)出予圖的所有連通分支都屬于p g 的p 一 色數(shù)是指g 有一個( p ，k ) 染色的最小值，記做x p ( g ) 若p 是只有一個圖日所 組成的集合，則( p ) 一染色也記為( 日，) 一染色，胎( g ) 也記為x h ( g ) 若日= 噩， 則x 日( g ) 就是通常所說的圖g 的點色數(shù)，也記為x ( g ) ，若p 是所有樹的集合，則 x p ( g ) 就是通常所說的點蔭度，也記為u a ( g ) 若p 是所有路的集合，則x 尸( g ) 就 是通常所說的線性點蔭度，也記為 z 口( g ) 一個圖g 的線圖l ( g ) 是指以g 的邊集為它的頂點集合，l ( g ) 中的兩個頂 點是相鄰的當(dāng)且僅當(dāng)它們對應(yīng)的邊在g 中是相鄰的一個圖g 的( p 1 ) 一邊染色 就是指線圖l ( g ) 的( p 1 ) 染色g 的p 邊色數(shù)是指g 有一個( p ，k ) 邊染色的 最小值，記做婚( g ) 若p 一 j 島 ，則( p 1 自) 一邊染色也就是通常所說的邊染色， 圈的邊色數(shù)x 7 ( g ) = x 乞( g ) 若p 是所有樹的集合，則x ，p ( g ) 就是通常所說的蔭 度，也記為口( g ) 若p 是所有路的集合，則( p k ) 一邊染色也叫線性女染色婚( g ) 就是通常所說的線性蔭度，也記為f d ( g ) x 2 。( g ) 是圖g 的線性蔭度，也記為 2 0 k ( g ) 本文所用術(shù)語和符號基本上與文獻【l 】中一致本節(jié)未介紹的其他圖論術(shù)語 將在必要時予以闡述 ( 二) 、線性蔭度問題的概念、應(yīng)用背景與研究概況 要講圖的蔭度理淪的歷史，首先得從圖的染色問題說起關(guān)于圖的染色問 題，首先起源于圖的點染色，如四色問題關(guān)于圖的點染色，至今已得到許多重要 的研究成果這里僅給出下面著名的b m o l c 8 定理： 定理1 2 1 1 】對任何圖g ，有x ( g ) ( g ) + 1 ；且等式成立當(dāng)且僅當(dāng)g 為奇 圈或完全圖 關(guān)j ：圖的邊染色，有著名的v i z i n g 定理： 3 f b ) g 不含弦4 圈即：不存在兩個共用一條邊的3 _ 圈特別地，g 不含有 相鄰的3 面進而，能夠得到g 中的每個頂點 至多與i d ( ) 2 j 個3 一面關(guān)聯(lián)從 而有如下斷言成立： 斷言1 對于任何頂點 ，有m 3 ( ”) l d ( 口) 2 j ( c ) 對于g 中的 x 因此邊z g 至多與日中的七條邊相鄰由于i a l 一4 ，因此存在某種顏色o g ，在 h 中那些與邊z 可相鄰的邊中，顏色d 至多使用次從而我們將邊$ 口染上顏色 n ，這樣就將c 擴展為整個圖g 的線件4 染色容易驗證這樣得到的染色是g 的 一個線性4 一染色因此，z 口( g ) 4 定理2 1 1 證明完畢 口 定理2 1 2 如果g 是一個( g ) 7 且不含弦4 圈的平面圖，那么址( g ) 4 證明只要證明g 是一個l 9 一遺傳圖，就可以由定理21 1 得到我們所要的 結(jié)果首先注意劍這樣一個事實，如果圖g 是不含弦k 圈的，那么g 的每個子 圖也是不含弦一“圈的因此我們只需證明g 具有性質(zhì)l 9 如果g 是空圖，顯然g 具有性質(zhì)l 。假設(shè)i e ( g ) j o 設(shè)日是g 的一個連 通分支，其中i v ( 日) i 2 ，因此，日是一個( 日) 7 ，6 ( 日) 1 ，且不含弦一4 - 圈的 平面圖如果d ( 日) s2 ，那么在h 中存在一條邊列，使得婦( 囂) 2 而且 d 日( 回+ d h 0 ) 2 + ( g ) 2 + 7 = 9 如果d ( 日) 3 ，那么由引理2 1 2 ，在日中存在一條邊z 口，使得婦( z ) + 婦( 口) 9 注意到，d g 0 ) = d 日扛) ，d g ( y ) = d = r ( ) ，以及e ( 胃) 曼e ( g ) ，從而有。g e ( g ) ，且 使得d g ( z ) + d g ( ) 9 因此，g 也具有性質(zhì)島 定理2 1 2 證明完畢口 對任何圖g ，我們有k ( g ) f 學(xué)1 由這個事實以及定理2 1 2 ，我們能得到 下面的結(jié)果： 推論2 1 2 每個( g ) = 7 且不含弦一4 _ 圈的平面圖g ，都有k ( g ) = 4 ( 二) 、不含弦。5 。圈的平面圖的線性蔭度 這一節(jié)，我們將證明每個不含弦一5 一圈的平面圖g 滿足猜想1 2 2 首先給出 這類圖的一個結(jié)構(gòu)性質(zhì) 引理2 2 1 若g 是一個d ( g ) 3 且不含弦5 一圈的平面圖，則g 含有一條 邊z ，使得d ( 。) + d ( g ) 9 證明我們將再一次使用反證法假設(shè)引理不成立，設(shè)g 是一個連通的反例， 從而g 具有如下性質(zhì)： 1 3 ( a ) d ( g ) 3 ( b ) g 不含有弦一5 - 圈特別地，我們有如。卜斷言： 斷言1 g 申不存在一個4 面與一個b 面相鄰的結(jié)構(gòu) 若斷言1 不成立，則假設(shè)g 中有一個4 一面 = 陋l $ 2 茹3 ?！颗c一個3 _ 面，2 相 鄰從而 與，2 至少有一條，至多有兩條公蓯邊如果 與如有兩條公其邊， 不妨設(shè)為z l z 2 和$ 2 。3 ，那么很容易得到在g 中頂點9 2 的度為2 ，這與性質(zhì)( a ) 矛 盾因此，面 與面，2 只有一條公共邊，不妨設(shè)為善1 2 2 即，2 = b z l z 2 】如果 位于 的邊界上，不妨= 0 3 ，則在點茁1 和點$ 3 之間至少存在兩條邊，這與我 們假設(shè)g 是一個簡單圖矛盾如果不位于 的邊界上，則我們能得到一個以 z l z 2 為弦的5 一圈z 1 3 ，眈黝0 4 0 1 ，而這是不可能的從而證明了斷言1 口 與斷言1 的證明類似，我們有如下斷言： 斷言2 g 中不存在一個凸面與兩個非相鄰的b 面相鄰的結(jié)構(gòu) 斷言2 表明每個度4 的頂點 都不可能與3 個連續(xù)相鄰的3 _ 面關(guān)聯(lián)由 這個事實，我們可以得到如下斷言： 斷言3 對于每個度4 的頂點 ，都有m 3 ( ”) 1 2 d ( ) 3 j ( c ) 對于g 中的每條邊，都有d ( $ ) + d ( y ) 1 0 為了得到矛盾，我們將再次使用權(quán)分配方法對于所有的z y ( g ) u f ( g ) ， 定義權(quán)函數(shù) ( z ) = d ( z ) 一4 因此，由引理2 1 1 ，有 銣( z ) = _ 8 z y ( g ) u f ( g ) 建立如下4 個權(quán)分配規(guī)則： ( r 1 ) 每個大點u 轉(zhuǎn)移；給每個與它相鄰的3 - 點，轉(zhuǎn)移；給每個與它關(guān)聯(lián)的孓 面 ( r 2 ) 每個6 一點 轉(zhuǎn)移 給每個與它關(guān)聯(lián)的3 一面 ( r 3 ) 每個5 點u 轉(zhuǎn)移j 給每個與它關(guān)聯(lián)的3 一面 ( r 4 ) 只要口( ，) 0 ，那么每個度5 的面，轉(zhuǎn)移叫( ，) 朋( ，) 給每個與其相關(guān)聯(lián) 的大點其中，盧( ，) 表示與，關(guān)聯(lián)的大點的數(shù)目 】4 假設(shè)，是一個度5 的面， 是一個與，關(guān)聯(lián)的大點由( r 4 ) ，我們直接可 以得到下面的結(jié)論： ( i ) 如果p ( ，) = d ( ，) ，那么，至少轉(zhuǎn)移 給 ； ( i i ) 女i i 果口( ，) o ，那么由( r 4 ) ，有 叫( ，) = 訓(xùn)( ，) 一p ( ，) 叫( ，) p ( ，) = 0 若d ( ，) = 3 ，則叫( ，) = 一1 設(shè)，= 【z 9 2 】i 并使得d ( 。) d b ) sd ( z ) 如果 d ( z ) = 3 ，那么由性質(zhì)( c ) ，有d ( v ) ，d ( 。) 7 由( r 1 ) ，和z 均要轉(zhuǎn)移；的權(quán)給， 從而， 11 叫( ，) 一l + ；+ 去= o 如果d ( 。) = 4 ，那么由性質(zhì)( c ) ，有d ( ) ，d ( z ) 6 由( r 1 ) 和( r 2 ) ，和z 均要轉(zhuǎn)移 的權(quán)給，從而也有 ( ，) 一l + 2 妄= o 如果d ( z ) 5 ，那么由( r 1 ) 一( r 3 ) ，z ，f ，z 均至少要轉(zhuǎn)移；的權(quán)給，因此， 叫7 ( ，) 一l + 3 妄= o 設(shè)u y ( g ) ，由6 ( g ) 3 ，有d ( 口) 3 如果d ( ) = 4 ，那么由權(quán)分配規(guī)則，u 既不轉(zhuǎn)移也不接受權(quán)因此，( ) = 叫( u ) = d ( 口) 一4 = o 若d ( ) = 3 ，則 ( ) = 一1 由性質(zhì)( c ) 知道 的每個鄰點均是度7 的點，因 此按照( r 1 ) ，這些鄰點要轉(zhuǎn)移 的權(quán)給u 從而，叫，( 口) = 一1 + 3 = o 若d ( u ) = 5 ，則伽( ) = 1 由斷言3 ， m 3 ( ) 1 2 d ( ) 3 j = 3 ， 1 5 假設(shè)m 3 ( ) = 4 在這種情況下，由斷言4 我們?nèi)匀挥兴? 口) 5 由斷言1 和 斷言2 ，我們很容易證明 恰與3 個度5 的面關(guān)聯(lián)因此，由( i ) ，有 r ( ) 3 ；= ； 如果n 3 扣) 4 ，那么 叫( ”) + r 扣) 3 + ； ；+ ；s 扣) 下面假設(shè)“3 ( ) = 5 設(shè)u 。，啦，t j 7 為以順時針順序攤列的u 的鄰點設(shè)， 為與 關(guān)聯(lián)的面，u 仇和口口i + l 是邊界邊，其中 = 1 ，2 ，7 ，下標(biāo)對7 取模由于 m ( ”) = 5 ，而且m 3 ( ) = 4 ，不失一般性，我們能得到如下結(jié)構(gòu)( p 1 ) 和( p 2 ) ： ( p 1 ) 如果t = 1 ，3 ，4 ，6 ，7 ，那么d m ) = 3 ；如果j = 2 5 ，那么d ( ) 7 ( p 2 ) = 卜口l 忱】，2 = 【口噸t 1 3 】，4 = 【 饑 5 】和，5 = 【”船鉑】均為3 一面；，3 ，6 和 ，7 是度5 的面 由( p 1 ) 和( p 2 ) ，我們看到，矗，6 ，7 中的每一個面均至少與一個3 _ 點關(guān)聯(lián)，因 此由( i i ) ，這些面至少轉(zhuǎn)移 的權(quán)給 由此得到r ( u ) i ，從而有 ”( ”) + r ) 3 + i ；+ ；= s ) 引理2 2 1 證明完畢 口 由引理2 2 1 以及與不含弦4 - 圈的平面圖的證明類似，我們能夠證明每個 ( g ) 7 且4 i 含弦一5 一圈的平面圖g 都是l 9 ，遺傳圖從而，我們能得到下面的 定理： 定理2 2 1 如果g 是一個( g ) 7 且不含弦一5 - 圈的平面圖，那么k ( g ) 4 推論2 2 1 每個( g ) = 7 且不含弦一5 圈的平面圖g ，均有f 口( g ) = 4 ( 三) 不含弦6 - 圈的平面圖的線性蔭度 引理2 3 1 如果g 是一個6 ( g ) 3 且不含弦- 昏圈的平面圖，那么g 中存 在一條邊z ，使得d ( z ) + d ( g ) 9 證明假設(shè)引理不成立，設(shè)g 是一個連通的反例因此，g 有如下性質(zhì)： ( a ) 6 ( g ) 3 ( b ) g 不含有弦一6 一圈 1 8 假發(fā)m 3 ( u ) = 5 ，則由性質(zhì)( e ) 有 似”) s8 一f i l = 5 又因為m 3 ( u ) = 5 且d ( ) = 8 ，觀察1 和觀察2 表明u 與一個度5 的面關(guān)聯(lián)因 此，由觀察4 得到r ( u ) ；從而， s 扣) s ；+ ；= a ； 4 + ；叫( u ) + r ( ”) 假設(shè)m 3 ( 口) = 6 f = 7 ! ； ! 質(zhì)( e ) ，有 禮3 扣) 8 一曇1 = 5 不失一般性，根據(jù)觀察2 和觀察3 ，得到唯一一種可能的情況：對于 = 1 ，2 ，3 ，5 ，6 ，7 有d ( 五) = 3 ；對于j = 4 ，8 ，有d ( 厶) 6 因此，由觀察4 ，我們能得到 r ( ”) r ( ，4 一”) + r ( ，8 一”) ；+ ；= ；， 以及 s ( 們；+ ；= 4 + ；s 扣) + r ) 下面假設(shè)d ( 口) = 7 ，從而 ( ) = 3 并且由性質(zhì)( d ) ，有m 3 ( v ) 5 如果m 3 ( ”) 1 ，那么 71 8 ( 口) ；+ ； 3 ”扣) + r ) 如果執(zhí)( 口) = 2 ，那么由性質(zhì)( e ) ，有珊( 口) s7 1 = 6 因此， s 扣) ：+ ；：3s 伽) + r o ) 假設(shè)m 3 ( ) = 3 ，那么由性質(zhì)( e ) 有禮3 ( 口) s7 2 = 5 由規(guī)則( r 1 ) ，得到 巾) ；+ ；= s 接下來我們將證明”至少與一個度5 的面關(guān)聯(lián)，使得r ( ) ，從而s ( ) 和z 咖，呲) ，但由 g 的平面嵌入知道這是不可能的因此，4 和，7 中至少有一個是度5 的面 ( a 2 ) 對于t = l ，2 ，5 ，有d 飯) = 3 如果，3 和，7 都是4 - 面，即，3 = f 地暑 4 】和 ，7 = 口 7 z 1 ，由于g 不含有弦一6 - 圈，那么肯定有= 口l 和z = 地但由g 的平 面嵌入知道這是不可能的因此，3 和，7 中至少有一個是度5 的面 2 1 ( a 3 ) 對十e = l ，2 ，4 ，硐d ( ) = 3 由觀祭2 得劍d ( ，3 ) 5 ( a 4 ) 對于i = 1 ，3 ，5 ，有d ( ，) = 3 由觀察2 得到d ( ，2 ) 5 假設(shè)m 3 ( ) = 4 ，那么由性質(zhì)( e ) 有n 3 ( ”) 7 2 = 5 如果珊( 口) s3 ，那么 s ) ；+ ；= 3 叫扣) + r 扣) 因此假設(shè)“3 ( ) 4 由對稱性，我們考慮下面3 種情況( b 1 ) 一( b 3 ) ： ( b 1 ) 對j 二 = 1 ，2 ，3 ，5 ，有d ( ) = 3 由觀察2 和觀察3 有d ( ，4 ) 6 ，因此由觀 察4 得到r ( ”) r ( ，4 一口) 另一方面，在這種情況下容易證明n 3 ( u ) 4 因 此， s ( 叼；+ ；= 3 ；= 3 + ；鈕p ) 十r o ) ( b 2 ) 對于i = 1 ，2 ，4 ，5 ，有d ( ，) = 3 首先由觀察2 有d ( ，3 ) 5 下面證明，6 和，7 中至少有一個面的度5 事實上，如果，6 和，7 都是4 - 麗，即，6 = p 挑口吲 和，7 = 【饑，7 刪l l ，那么又由g 不含有弦- 6 _ 圈可以得到”= 和2 = 銣 日是這樣 將會得到g 中一個以 嘶為弦的6 - 圈帆1 拋姐獅螄u 不失一般性，我們假設(shè)d ( ，6 ) 5 由觀察4 ， r ( ”) ，( 。) 十，( ，6 。) ；十；：； 如果n 3 扣) = 4 ，那么 s ) ；+ ；= 3 ； 3 + ；伽扣) + r 扣) 如果n 3 ( “) = 5 ，那么對于 = 1 ，3 ，4 ，6 ，7 ，有d 慨) = 3 因此由觀察4 ， r ( v ) r ( ，3 + ”) + r ( + ”) ；+ ；= ； 從而， s ( ”) s ；+ ；= 3 ；= 3 十；s 扣) + r 扣) ( b 3 ) 對于t = l ，2 ，4 ，6 ，有d ( ，) = 3 由觀察2 可以得到對- rj = 3 ，5 ，7 ，有 d ( 矗) 5 因此， r ( ”) t ( ，3 一”) + r ( 一”) + r ( ，7 一”) ；+ ；+ ；= ； 而且，在這種情況下，容易證明n 3 ( 口) s4 因此， s 。) ；+ ；一3 ； 3 + ； ( ”) + r 。) 最后假設(shè)m 3 ( ) = 5 ，那么由性質(zhì)( e ) ，有禮3 ( ) 7 3 = 4 不失一般性，對于 所有的2 = 1 ，2 ，3 ，5 ，6 ，有d ( ) = 3 從觀察2 和觀察3 可以得到d ( ，4 ) ，d ( ) 6 ，因 此由觀察4 ，有 r ( ”) r ( ，4 一”) + r ( 一”) ；+ ；= ； 如果”3 ( w ) 3 ，那么有 s ) ；+ ；= 3 ； 3 + ；”( ”) + r 扣) f 面假設(shè)n 3 ( 口) = 4 在這種情況下，容易得到，嘶是3 一點，口1 ，螄中至少有一個 點是墨點從而，由觀察4 得到 巾) ；+ j = 品， 以及 s ( ”) ；+ ；= 3 ； 3 + 殺s ( ”) + r ( ”) 引理23 1 證明完畢幾 定理2 3 1 如果g 是( g ) 7 且不含弦一昏圈的平面圖，那么f n ( g ) 4 推論2 3 1 每個( g ) = 7 且不含弦一6 _ 圈的平面圖g ，都有l(wèi) o ( g ) = 4 圈稱g 上的點為外點，其余的點為 推出 令 吲郵【堂乒j 噩= + t ，疋= 墨 對于所有的$ y ( g ) ，我們有 屯( z ) = 蛔( 茁) 此外 屯( u ) ：1 m 旺( 掣1 ，2 ) ， 屯( 歸l + 咄( 哪! + 【堂# j = 掣1 ， 以及對所有的。y ( g ) u ，) ， 如i ( z ) = d 叫( z ) 故nu 乃是g 的一個滿足定理要求的邊分解 情況2 存在兩個相鄰的2 - 點釷和 定義g 7 = g 一由歸納假設(shè)，g ，可以邊分解為兩個森林墨和正，使得對 于每個z y ( g ) 且i = l ，2 ，有 卿( 茁) m 。 f 苧掣洶 不妨設(shè)讓， 的另一個鄰點分別為“7 ，u 若礎(chǔ)， t ，e ( 掣) ，則令 丑= ，馬= + 伽 對于所有的z y ( g ) ， d n ( o ) = d 列( ) 另一方面 電( 。) ：1 。娃“掣1 ，2 ) ， 如2 ( 。) ：l o 若d g ( u ) 8 ，則 ( ”) 伽( 釘) 一妄( 禮2 ( 付) + n 3 0 ) + 黿3 0 ) ) 1 d g ( ”) 一4 一言d g ( 可) 1 = 言d o ( ) 一4 o 若d g ( ) = 3 ， 的每個鄰點的度8 ，因此由( r 1 ) 每個鄰點分配 給u ，從 而甜7 p ) 一l + 3 = ； 若d g ( ) = 2 ，則口與兩個度8 的點相鄰若 是一個反常2 - 點，由斷言3 ， u 與一個度6 的面關(guān)聯(lián)從而由規(guī)則( r 1 ) 和( r 2 ) ，t ，( w ) 一2 + 1 + 2 t = o 否 則， 與兩個度5 的面關(guān)聯(lián)，從而由規(guī)則( r 1 ) 和( r 2 ) ，( ) 一2 + 4 = o 【3 2 ) k w l 血，ld t 0 n g8 n dw f w 姐舀t h e1 i n e a r2 - 曲o r i c i t yo fo u t e r p l 蛆盯 g r a p h 8 【j 】，a r 8c o 廿曲i n ，2 0 0 4 ，7 3 ：1 3 - 2 2 【3 3 】y h b u ，s o m er 鵲u l t 8 o np l 蚰盯g r 印h bo fc l 夠s1 【j ，a d v 帥c ei nm a t h ，2 0 0 4 ，3 3 ： 3 7 5 3 7 7 3 4 w f w a n g ，p l a n 8 rf a p h s t h a th 帆n os h o r tc y c l 髓w i t hac h o r da r e3 c h o o 鼯b l e 【j 】， t 甑w a i l e j m 砒h ，t o8 p p e 缸 【3 5 】w f w h g8 n dk w l i h ，l i g h t8 u b 釅印h 8 姐de d g e - 吐l 0 0 8 8 b i l i t yo fp l 蛐a rg r a p l l 8 w i t h o u t3 - c y c l 髑o r4 c y c l 【j 】m 瑚絲u io x j m a t h s d ，2 0 0 4 ，2 0 ：3 5 3 - 3 7 6 【3 6 】w f w a n g8 n dk w l i h ，c h o 嘴8 b i l i t y 眥de d g ec h o b b i u t yo fp l a n 時g r p h sw 沁h o u t 6 v ec y c l 鶴【j 1 ，a p p l m b t h l e t t ，2 0 0 2 ，1 5 ( 5 ) ：5 6 l - 5 6 5 3 7 】w f w a n g8 n dk wl h ，s t r u c t u r a lp r o p e r t i e 8b n de d g ec h 0 0 s b i l i t yo f p l a n 8 rg r 8 p h s w i t h o u t6 c y c l e s 【j 】1c o m b i np r o b 8 b c o m p u t ，2 0 0 1 ，1 0 ：2 6 7 - 2 7 6 【3 8 】kw l i h ，w fw 觚gb n dx z h u ，c 0 1 0 r i n gt h e8 q u r eo fak 4 一m i n o r 如eg r a p h ，【j 】， d i s c r e t em a t h ，2 0 0 3 ，2 6 9 ( 1 3 ) ：3 0 3 - 3 0 9 【3 9 】k k e d l