（基础数学专业论文）线图的几个性质.pdf

摘要 本文就图的哈密顿指数、类指数以及线图的次泛圈性进行了讨论，得出了如下 一些结果 ( 1 )设g 为连通图，a ( g ) 七2 ( k 为整数) ，g = gk ( i s2 k + 3 ) ，若 ( g ) t ， 那么 ( g ) = h ( g7 ) ( 2 )若图g 有含2 ) 个圈的2 一因子，那么l ( g ) 也有含个圈的2 一因子 ( 3 )若g 是点泛圈可序图，那么l ( g ) 也是点泛圈可序图 、 、 ( 4 )若图g 有两个边不交的哈密顿圈，那么l ( g ) 也有两个边不交的哈密顿圈 ( 5 )若g 是1 一哈密顿图，那么l ( g ) 也是1 一哈密顿图 ( 6 )若g 是泛连通图，那么l ( g ) 也是泛连通图 ( 7 )设g 是n 阶简单图m 7 2 ) ，满足q l ( g ) 8 ，围长g ( a ) 5 且q ：( g ) 2 4 2 n + 1 时，则其线图l ( g ) 是次泛圈图且2 2 + 1 这个界是最好可能的、， ( 8 )设g 是n 阶简单图m 7 2 ) ，满足鼋( g ) 8 ，围长g ( g ) 4j l q z z ( g ) 一2 9 ：( g ) 鼢，则其线图( g ) 是次泛圈 i 旧_ 8 n 这个界是最好可能的 关键词：哈密顿指数，枝，收缩，2 一因子，点泛圈可序图，泛连通图，卜哈密顿图 次泛圈图泛圈图 a b s t r a c t i nt h i st h e s i s ，w em a i n l yt a l ka b o u tt h ep r o p e r t i e so fh a m i l t o n i a ni n d e xa n dl i k e i n d i c e si ng r a p h ，a n ds u b p a n c y c l i c i t yi nl i n eg r a p h w eh a v et h ef o l l o w i n gr e s u l t s ( 1 ) l e tgb eac o n n e c t e dg r a p h ，g - a l c0 5 放+ 3 ) i f i l ( g ) 2 k 2 2 ，a n dh ( c ) 2 后( k 6 z ) ，t h e nh ( g ) 一h ( g ) ( 2 ) i fgi sag r a p hw h i c hc o n t a i n sa2 - f a c t o rw i t ht ( 七22 ) c y c l e s ，t h e nl ( g ) a l s o c o n t a i n sa2 - f a c t o rw i t hkc y c l e s ( 3 )i fgi sa g r a p hw h i c h i s v e r t e x p a n c y c l i co r d e r e d ，t h e n ( g ) a l s oi s v e r t e x p a n c y c l i co r d e r e d ( 4 )i fgc o n t a i n st w oe d g e d i s j o i n th a m i l t o n i a nc y c l e s ，t h e n ( g ) a l s oc o n t a i n s t w oe d g e d i s j o i n th a m i l t o n i a nc y c l e s ( 5 )i fgi s1 - h a m i l t o n i a n t h e n l ( g ) a l s oi s1 - h a m i l t o n i a n ( 6 ) i fgi sa g r a p hw h i c h i sp a n c o n n e c t e d ，t h e n 己( g ) a l s oi sp a n c o n n e c t e d ( 7 ) l e tgb eas i m p l eg r a p hw i t hn 如7 2 ) v e r t i c e sw h i c hs a t i s f i c e sc o n d i t i o no f q 1 ( g ) 苫8 i f g ( g ) 5 ，吼( g ) 2 2 以+ 1 ，t h e n ( g ) i sas u b p a n c y c l i cg r a p ha n dt h e b o u n do f 2 丢鬲i st h eb e s tp o s s i b l e ( 8 ) l e tgb eas i m p l eg r a p hw i t hn 西7 2 ) v e r t i c e sw h i c hs a t i s f i c e sc o n d i t i o no f 饥( g ) 8 i f g ( g ) 4 ，q ；( g ) - 2 q z ( g ) 8 n ，t h e n ( g ) i sas u b p a n c y c l i cg r a p ha n dt h e b o u n do f8 ni st h eb e s tp o s s i b l e k e y w o r d s ：h a m i l ( o n i a ni n d e x , b r a n c h ，c o n t r a c t i o n ，2 - f a c t o r , v e r t e x p a n c y c l i co r d e r e d g r a p h ，p a n c o n n e c t e dg r a p h ，1 - h a m i l t o n i a n , s u b p a n c y c l i cg r a p h ，p a n c y c l i cg r a p h 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表 示谢意。 学位论交作者签名：乞雯韵 签字日期：2 护7 年歹月习日 f f 学位论文版权使用授权书 本学位论文作者完全了解江西师范大学研究生院有关保留、使用 学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印 件和磁盘，允许论文被查阕静借阅。本人授权江西师范大学研究生院 可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：尧雪韵 签字日期：岬年步月0 7 日 导师签名：训脓l 呜 签字日期：撕7 年厂月讶日 线图的几个性质 第一章预备知识与引言 1 1 预备知识 术语和记号 本文考虑的图g = ( g ) ，( g ) ) 是有限无向简单图，未定义的术语和符号参见 文献 1 】h 的两个子图g l ，g 2 在日中的距离( 记为如( g 1 ，g ：) ) 定义为 m i n 如u l , u 2 ) ：“。y ( g 1 ) 且“：v ( g o ) ，其中d 。u v u 2 ) 表示日中从u 1 到u 2 的最 短路的路长，用c 表示顶点个数为f 的圈 图g 的线图( 记为l ( g ) ) 是指以g 的边集为顶点集且( g ) 的两个顶点( 即 g 的两条边) 邻接当且仅当它们在g 中是邻接的对于整数，l z l ，1 次迭线图( 记 为参( g ) ，递归地定义为( f 一1 ( g ) ) ，。其中。f ( g ) ，g 且口( 0 ) 。三( g ) 图g 的 h a m i l t o n i a n i n d e x ( 即哈密顿指数，记为i i ( g ) ) 是指使p ( g ) 为哈密顿图的最小 整数n ，记k ( g ) - v e v ( a ) ：a a v ) - i ) 和形( g ) 一y ( g ) 、k ( g ) g 中的一条路叫做枝 ： 是指它的端点在矽( g 1 中且内点均在心( g ) 中如臬二条枝的长度为l ，那么它就 没有内点用占( g ) 表示g 中所有的枝集合记蜀( g ) 一 6 b ( g ) ：y ( 6 ) n k ( g ) 一神 设日是g 的子图，记( g ) 一 b 6 b ( g ) ：e ( b ) c e ( h ) ) 设g 是连通图，令e 巩( g ) 表示g 中满足下列条件的予图h 的集合( 其中 是整数且后2 2 ) ( f ) h 的每一个顶点部足偶度，即对石矿( h ) 都有d 。0 ) z 0 ( r o o d 2 ) ； a f 6 ) ( “) k ( h ) cuk ( g ) c y ( h ) ； ( f 盯) 对于日的任何子图只，都有d 。( 臣，h q ) 主七- 1 ； ( f v ) 对于g 中的任何枝6 ，若e ( 6 ) n e 饵) 一妒，都有i e ( 6 ) i s 七+ 1 ： o ) 若6 b ( g ) ，则i e p ) ic 七 线图的几个性质 设f 为g 的子图，g f 表示由图g 收缩子图f 中所有边，并将产生的环删除 而到的图，1 9 8 8 年c a t l i n 用这种收缩方法研究一个图g 是否有生成回路o l ，表 示由图g 将子图f 的所有顶点看作一个新的顶点( 则g 中两个顶点都属于 v ( f ) 的边变成了环) ，并将产生的每个环用与关联的悬挂边( 有一个顶点度数 为l 的边) 取代而得到的图可知旧( g ) l = i e ( g i ，) | g f 与g i ，删除新增悬挂边是 等价的 定义1 1 图g 有一个泛圈序是指顶点集y ( g ) 可以按这样的顺序排列，( 对所 有3 s k 量p ( g ) 1 ) 由前七个顶点导出的子图都是哈密顿的g 是点泛圈可序图是 指：v e v ( a ) ，g 都有一个以x 为起点的泛圈序 定义1 2g 含有一个控制k 一系统是指g 有七个边不交的回路和星形( 星形 是指图k 。，一芑3 ) ，且满足g 的每条边要么是某个回路或某个星形中的一条边，要 么与某个回路的_ 条边相邻 一 定义1 3 若p 一h 吒表示一条迹( 或路) ，且e 0 ) 一编，乞，气) 表示满足 巳一q 一 ( 1 量f 七) 的边集，那么p 为g 中的一条饥，唯) 一迹( 或( v o ，h ) 一路) ，p 也 是一条眩，气) 一迹( 或瓴，气) 一路) 其中h ，屹，屹。称为p 的内点，巳，气称为p 的端 边 一 定义1 4 设p 是g 的一条迹，令a ( p ) 一忙( g ) ：e 与p 的某个内点关联) 定义1 5 g 是1 一哈密顿的( 记作啊) 是指g 含哈密顿圈，j g v v v ( g ) ，图 g v 也含哈密顿圈 定义1 6g 是泛连通的( 记作p c ) 是指任取两个不同顶点“，v e v ( g )任 意整数七q 。 ，v ) s 七s i v ( o ) l 一1 ) ，g 中都有长为七的 ，v ) 一路 定义i 7g 是边哈密顿的( 记作曲) 是指对于g 中任意边e ，g 中都有哈 密顿圈经过它 定义1 8 g 是哈密顿连通的( 记作h c ) 是指任取两个不同顶点“，v e v ( o ) ， g 中都有长为l y ( g ) l - 1 的0 ，v ) 一路 定义1 9 g 是泛圈的( 记作p ) 是指对任意整数七( 3 s 七一- i v ( g ) - 1 ) ，g 中都 2 线图的几个性质 定义1 1 0 g 是点泛圈的( 记作节) 是指任取顶点u e v ( a ) 任意整数 k ( 3 s ks 旷( g ) f 一1 ) ，g 中都有长为七的圈经过点砧 定义1 1 1 g 是边泛圈的( 记作e p ) 是指任取边e e e ( g ) 任意整数 k ( 3 5 k s j v ( a ) l 一1 ) ，g 中都有长为七的圈经过边e 设g 是一个非空图，p 表示一种性质，下面定义图g 的p 指数( 记作p ( g ) ) ： p ( g ) ：m i nk ：图r ( g ) 有性质p ) ； 非空 i 。；否则 当p e h ，啊，p ，叩，e p ，e h ，h c ，p c l ，显然对任意图g 都有： ( g ) s p ( g ) 主 ( g ) 蔓节( g ) s p c ( g ) ，。 h ( g ) ：哆( g ) s i l c ( g ) s ，c ( g ) ， e h ( g ) s 印( g ) i jh ( g ) 主啊( g ) 定义1 1 2 图g 是k t r i a n g u l a r 是指g 的每条边至少包含在g 的k 个三角形中 一条边e = u v e e ( g ) 在g 中的度数记为d 0 ) ，其中d ( e ) - a ( u ) + d ( v ) 记 q l ( g ) 。m i n d ( u ) + d ( v ) ：m ，e ( g ) 吼( g ) 一m i n d ( e i ) + e ( e j ) ：弓q 圣e 犯( g ) ) 且 岛，e ，e ( g ) ，表示g 中两条独立边的最小度和设h 是g 的一个子图，记e 僻) 为一 子图日所有边的边集，e ( h ) - e e e ( g ) ：e 与日中至少一个点相关联 1 e ( h ) l ，f ( 日) ，i i x h ) i 一；口) ，玄2 ( 日) 一 ( 乞，e ，) ：巳，巳e ( 日) ，弓e j i 壬e ( g ) ) 图g 的围长指的是g 中最小圈的长度，记为占( g ) 图g 的周长指的是ge e 最大圈的长 度，记为盯( g ) 图g 的闭迹是指g 的欧拉子图，即g 中每点度为偶数的连通子图 所以据此定义，由单个顶点导出的平凡子图也是闭迹令a ( g ) - 忙：g 中包含长为七 的圈，若a ( g ) - 3 ，4 ，i v ( g ) l 】_ ，则图g 称为泛圈图；若a ( g ) - 3 ，4 ，c r ( g ) ，则图 g 称为次泛圈图1 1 1 1 设日是g 的一个子图，若s 是日的一个子图，那么s 中所有点在日中的度和 3 线图的几个性质 用“( s ) 表示( 日= g 时，简记为d ) ) ，即d 。岱) - 罗d 。0 ) n ( g ) 一m i n ( a ( p ) ：p “d r f ! s ) 是g 中长为f 一1 的路 ，令6 ( g ) 一p l ( g ) ，鼋1 ( g ) t p ：( g ) 用f 表示下面这样的图：其 阶数尼= l ( m o d 3 ) ，设c 1 ，c 2 ，c 扣i ) ，是o 一1 ) 3 个边互不相交且长都等于4 的圈， f 7 是由圈c 1 ，q 一，c ( - l v 3 构成的且这0 1 ) 3 个圈在，中恰好有一个公共点，且 e ( ，) - e ( c 1 ) u e ( c ：) u u e ( c ( n - 1 ) 3 ) 四j l v ( e ) i ；厅，成( f ) a ( 2 n + 1 6 ) 3 相关结果 h a r a r y ，n a s h w i l l i a m s 和b o n d y 在文【8 和【1 0 】中给出哈密顿线图的重要定 理，这些定理是后来大多数相关结论的基础 定理1 i s 图g 的线图是哈密顿图当亘仅当g 有一个闭迹c ，使得i ( c ) ： i e ( g ) i 芑3 定理1 【1 们图g 的线图包含一个长为k 3 的圈当且仅当g 有一个闭迹c 且 一 e ( c ) s k s ( c ) ： 在文【3 】，【1 6 】，【1 7 1 ，【1 9 】和【2 0 】中得到了许多 ( g ) 上界的定理，下面是其中 对h ( a ) 的上界描述相对简单的定理一 定理3 脚设g 是一个连通图且不含顶点个数为2 的圈，玎2 ( ，l 为整数) ， 则 ) s n 当且仅当e 玑( g ) 一驴 定理4 1 6 1 设g 是连通图( 路除外) ，若6 ( g ) 苫3 ，那么 ( g ) s 2 定理5 1 7 1 设g 是n 阶简单连通图( 路除外) ，那么h ( a ) s 月一( g ) 定理6 埘设g 是连通图( 路除外) ，那么 ( g ) s d 缸( g ) 一1 ( d 谊( g ) 是图g 的 直径) c l a r k ，w o r m a l d 和h o n g - j i a n l a i 等人就图的哈密顿类指数得出了许多定理 定理7 唧 若g 是2 - 连通图且g 是1 一t r i a n g u l a r ，那么l ( g ) 是泛连通图 定理8 唧 若g 是连通图且g 是2 一t r i a n g u l a r ，那么( g ) 是泛连通图 4 线图的几个性质 定理9 旧 若g 是哈密顿连通图( 边哈密顿图，泛圈图，点泛圈图，边泛圈 图) ，那么l ( g ) 也是哈密顿连通图( 边哈密顿图，泛圈图，点泛圈图，边泛圈 图) 熊黎明，等就线图的次泛圈性得到了以下几个最好可能的结果： 定理1 0 1 1 设g 是n 阶简单图0 7 2 ) ，围长占( g ) 5f iq 。( g ) 丽，则其线 图l ( c ) 是次泛圈图，且结果是最好可能的 定理1 1u 1 1 设g 是厅阶简单图o 2 7 2 ) ，围长g ( g ) 乏4 j | q 2 ( g ) 一q l ( g ) 2 n ，则 其线图l ( g ) 是次泛圈图，且结果是最好可能的 定理1 2 设g 是一个，l 阶连通图，若g 满足下面一个条件： ( i ) 1 2 1 p ：( g ) ( 石鬲+ 1 ) 2 0 2 6 0 0 ) ；，+ ( i i ) 【1 3 】岛( g ) o + 6 ) 2 0 乏7 6 ) ；， ： ( i i i ) 1 3 1p 4 ( g ) ( 2 n + 1 6 ) 3 ( n 7 6 ) ， 那么l ( g ) 是次泛圈图且肛( g ) 的界都是最好可能的 定理1 3 1 川设g 是一个月02 1 4 6 ) 阶连通图，若成( g ) ( n + 1 0 ) 2 ，那么( g ) 是次 ， 泛圈图( 除非g 同构于图f ) 而且n ( g ) 的界是最好可能的，即使在( g ) 为哈密顿图 的条件下也是最好可能的一 线图的几个性质 1 2 引言 在图论这门学科发展迄今的三百多年历史中，哈密顿图的研究起着非常重要 的作用，是图论方向众多专家研究的重点和难点围绕着哈密顿图的性质讨论也 定义出了很多不同的概念，如图的哈密顿指数及图的哈密顿类指数，哈密顿图的 泛圈性等 1 9 6 8 年c h a r t r a n d 提出了哈密顿指数这个概念，并于1 9 7 3 年给出树的哈密顿 指数公式1 9 8 8 年c a t l i n 提出了用收缩方法研究一个图g 是否有生成回路许多人 应用c a t l i n 的收缩方法得出许多关于哈密顿线图的结论，这个方法也被应用到研 究图的啥密顿指数l a i 和c a t l i n 等人应用收缩方法给出了与枝有关的哈密顿指 。 数的上界；s a r ai n 证明了一个简单图g 哈密顿指数是小于等于p ( g ) l _ ( g ) 熊 - 黎明通过图g 给出迭线图f ( g ) 0 2 ) 为哈密顿图的充要条件，并得到许多关于哈 密顿指数更好的结果哈密顿类指数主要包括p ( g ) ，v p ( a ) ，e p ( a ) ，p c ( a ) ，e h ( g ) ， h c ( a ) ，啊( g ) 等而哈密顿连通性，泛圈性及点泛圈性的研究较多( 特别是在无爪。 图中) 1 9 7 1 年j a b o n d y 在j c o m b i n a t o r i a l t h e o r yb 发表的论文p a n c y c l i cg r a p h s i 中，最早提出了泛圈图这个概念在以后的三十多年中，越来越多的研究人员从不 同方面投入了深入探讨，从而引申了很多课题的发展例如：分别从最小度，边 数，o ( “) 及0 0 1 ) 类型图，无爪图，哈密顿图等方面考虑图的泛圈性；从点独立数，哈 密顿图，最小度，等方面考虑线图的泛圈性；以及s t e p h a nb r a n d t ，r a l p hf a u d r e e ， w a y n eg o d d a r d 于1 9 9 8 年在j g r a p h t h e o r y 中发表的w e a k l yp a n c y c l i cg r a p h 中 定义了弱泛圈图，并对此类图的条件进行了深入研究熊黎明1 9 9 8 年在d i s c r e t e m a t h 发表的论文e d g ed e g r e ec o n d i t i o n sf o rs u b p a n c y c l i c i t yi nl i n eg r a p h s 中首次 线图的几个性质 定义了次泛圈图，主要从边度以及路度等条件入手，得出的结果都是与图的线图 有关而且都是最好可能的 7 线图的几个性质 第二章收缩圈不影响图的融砌懒玩妇 2 1 引言 熊黎明等在 3 中证明了收缩连通图g 中由度数大于等于3 的点生成的子图 的所有非平凡分支不会影响图g 的h a m i l t o n i a ni n d e x 由 4 可知，一个图收缩 圈c 3 并不会影响它的h a m i l t o n i a ni n d e x ，但收缩q ( i 皂4 ) 却不能保证 h a m i l t o n i a nh l d e x 不变，本章将证明连通图在满足一定条件下收缩e ( f2 4 ) 并不 影响它的h a m i l t o n i a nb 2 d e x ，且圈可收缩的长度范围是最好可能的 2 2 主要定理及其证明 引理1 d 1 设g 是欧拉图且日为g 的子图，那么c h 也是欧拉图； 。 定理2 1 设g 为连通图， ( g ) - - k 2 令g t g b ( f s 批十3 ) ，若 ( g7 ) 2 ，( k 为整数) ，那么h ( g ) 一h ( c ) 证明设在g 中由收缩g 中c f 的顶点集而得到的顶点记为由 g t g k ，有 ， ? 。 断言1( 除了g 中两个端点都属于y ( c ) 的枝以及g 中新增的悬挂边) g 和g 有相同的枝集合 下面我们先证 ( g7 ) s ( g ) 由 ( g ) 2 2 及定理3 ，j 日双( g ) 令日7 是由 h lc 删除新增悬挂边而得的图下面证( ，) ( g ) ，即证明h 满足定理3 中 属于e 以( g ) 的五个条件由引理l 可知h 满足( f ) 由h 满足何) 知h 也满足 “f ) 由断言1 及h7 的定义知h 满足 ) 和d ) 为证明7 满足( i i i ) ，只需考虑( 使 如僻7 ，日一k ) - - 2 ) h 的子图k 令k = h i v ：u 嘲， 其中 巧。v ( k ) n y ( g ) ，吆”一 x l x e v ( q ) ，d a ( x ) a 3 ( 当v c , 矿暖，) ) 或g ( 当屹隹y ( k ” 明显，k c _ h ，令p 为g 中一条从k 到h k 的最短路，令p 7 - - g7 陋o ) n e ( g7 ) 】， 则p 7 是 g 7 中一条从 k 到 日一k 的路， 所 以 r 线图的几个性质 如，( k ，h 一k ，) s 旧0 ) i i _ e p ) i d a ( k ，h - k ) 8 n ，则其线图( g ) 是次泛圈图且跏这个界是最好可能的 ， 为了证得上面两个定理，先证明下面3 个引理 。 引理a 设g 是，l 阶简单连通图；满足g ( g ) 芑5 ，q i ( g 苫8 ，且其线图l ( g ) 包含q 。 不包含c ，则有：( i ) g 有无弦圈g 。但不包含长度为尼的圈，其中里兰 ks 坍 二 ( i i ) 肼( 4 一一吼+ 4 ，( 吼一4 ) 证明( i ) 设g 满足引理假设条件，由定理2 ，g 包含一个闭迹c ，满足 ， 4 一 r。 。 ( c ) 臃+ 1 ( c ) 事实上( c ) m t n + 1 否则，如果5 ( c ) 墨m ，则。l ( g ) 中包含圈巳， 矛盾因为瑶。( g ) 8 ，所以a ( g ) 4 ，则( g ) 必然包含每个长从3 到a ( a ) 的圈，所以 ，”( g ) + 1 e ( c ) ；，h + 1 a ( g ) + 2 2 q l ( g ) 2 + 2 6 由于c 是一个闭迹，必存在边不交的圈d l ，d 2 ，d r ，使得c = u 2 断言1 若c 是g 的一个圈时，c 一定是无弦的 否则，若c 有弦，设c 是满足包含c 的恰好一根弦，且其它边都在c 上的所有 圈中的最长圈显然有e ( c ) 1 2 e ( c ) s ( c ) 在计算d ( v ) 中，e ( c7 ) 中每条边至 l 多被计算了两次，在d 0 ) 中，v ( c ) 中每点被计算两次，因此，在计算d 0 ) 中， #t4il：10i 云( c ，) 中每条边至多被计算了四次所以 线图的几个性质 ( c ，) z 毒，d ( e ) 4 e ( c ) q , 4 ，e ( c ) q , 8 乏坍+ 1 另一方面，( c ) 忙( d l - v ( c ) ) | ， 矛盾所以，r r 制j 1 因此，断言2 成立 由断言1 ，断言2 可知g 有无弦圈巳。且不包含长为的圈g ，其中竺芸 ks 肌 因此，( i ) 成立 ( i i ) 由( i ) 可设c 是g 中的无弦+ 1 ) 一圈由口。( g ) 8 ，v u v e ( g ) ，d ) + d ( d2 吼( g ) 8 ，若c 是g 的哈密顿圈，由c 无弦可知，d 0 ) + d p ) 1 4 8 ，故c 不是 g 的哈密顿圈因此，可设存在点u e v ( g ) v ( c ) 由已知g ( g ) 苫5 ，不能与c 上两 个距离2 的点相邻但如果“与c 上两个距离3 的点相邻，则会使得g 包含圈c ， 且f ( c ) 2 2 2 n + 1 ，则占( g ) 蔓( g ) + 1 证明因，l 7 2 ，i 孜q 2 ( o ) 22 5 设g 满足引理假设条件，c 是g 中的最短圈，即 s ( c ) 一g ( g ) 下面分两种情况讨论： 情况16 ( g ) - 1 设d ( v ) 一6 ( g ) - 1 ，设u v e ( a ) ，且b 与u s 不相邻，则2 a ( g ) + ( ( g ) + 1 ) 2 d p ) + d ( u v ) 毒q 2 推出a ( g ) ( q ：- 1 ) 3 反证，假设( c ) 一g ( g ) 2 ( g ) + 2 ，( c ) 苫( q z - 1 ) 3 + 2 1 0 ，则对v “矿( g ) 矿( c ) ，有陋v e ( g ) ：v 矿( c ) ) | s 1 ( 3 ) ，否则会产生一 个比c 更小的圈，这与c 是g 中的最短圈矛盾令巨( c ) ； e ；u v e ( c ) ：u 或v 与 g - 矿( c ) 的孤立点邻接 ，易( c ) 一( c ) 置( c ) ，即e z ( c ) = p 一“v e ( c ) ：口和v 都不 - 与a - v ( c ) 的任何一个孤立点邻接 ( c ) a 矿( g 【易( c ) 】) 令 霹( c ) 。 ，p 岛，e ，易( c ) ：岛p ，硭e ( g ) ) ) 情况1 1 旧( c ) - o ( & 0 恒( c ) l - l e ( c ) 1 ) 线图的几个性质 由c 的选择可知，v x v ( c ) ，存在一个集合 p j ， p i ) 是q ) 一2 ) 条长为2 的 路组成的集合，使得y ( a ) n 矿( c ) 一缸 ，v o , , ) n v ( p ，) - 缸，o - ，) 记毋为所有这样 路的集合，则昱中任何两条路在g 中至多有1 个公共点( 即若n ，p ，是同一个点x 产 生的两条路，则有p inp ，一扛，否则相交为空集) 则 - i - ( c 邶( c ) l | ( ( 钠酞川。4 恻邓) 。3 ) ) 2 似c ) 3 )( 畸 】e e f c )， 2e ( c ) q 2 4 2 e ( c ) ( 4 ) 。 因为鼻中每条路帮会产生一个点? 矿( g ) 、y 岳( c ) ) ，由上面( 3 ) ，( 4 ) 可智、 p ) + d ( e ) ) 一4 e ( c ) ( ( c ) 一3 ) n 2 ；( c ) + l 墨i = ( 擘! 。；! ! 旦_ i 磊i 己i ：j i _ + s ( c ) ) 七l 置i o 乏2 。( c ：4 2 s ( c ) ) + s ( c ) = 导r ( c ) ：璺( q ：一1 ) 3 + 2 ) 一，矛盾 情况1 2 i e x c ) l 。2 ( 即恢( c ) 卜；( c ) 一2 ) 设( c ) 一p ，厂 在易( c ) 中每条与p 或，相邻的边有0 ( c ) 一4 ) 种选法选取 艺( 0 中另外一条边，使得它们相互独立；而在易( c ) 中每条与e 和，都不相邻边有 0 ( c ) 一5 ) 种选法选取e 2 ( c ) 中另外一条边，使得它们相互独立在易( c ) 中有两条 边与e 或f 相邻，( s ( c ) 一4 ) 条边与e 和，都不相邻在计算 ，( d ( e j + a ( e 伪 椭 肚 “， 时，因c 是无弦的，所以e 2 ( c ) 、e 2 ( c ) 中每条边最多被重复计算2 ( ( c ) 一4 ) 次， 易( c ) 中每条边最多被重复计算4