（运筹学与控制论专业论文）无三角形的弱泛圈图.pdf

硕士学位论文 m a s t e r st h e s i s 摘要 取u 苊 陌广1 目早图，那呆盯十仕葸阴整毅h3 ，g 中笛有长匿为， 的圈，则称g 为泛圈图；如果g 中含有长度在围长和周长之间的所有圈，则称 g 是弱泛圈图。关于泛圈图，b o n d y ( 1 9 7 1 ) 证明了下面经典定理：每个边数至 少为了n 2 的船阶h a m i l t 。n i a t l 图是泛圈图或完全二部图。而后，b r a n d t ( 1 9 9 7 ) 改 进了b 。n d y 定理，证明了下面定理：每个边数至少为垒丢坚+ 1 的阶非二部 图是弱泛阢并提出猜想：每个边数至少为h s 的删e 部图是弱 泛圈图。随后咖s 和t n 。m a s o 邮哟，证明：每个边数至少为恻s ， 的门阶图是弱泛圈图或二部图。在本文中，我们证明对无三角形的图，b r a n d t 的猜想成立，郎每个边数至少为怿卜+ s 的行阶无三角形的非二部图是弱泛 关键词：弱泛圈图无三角形非二部图 a b s t r a c t l e tag r a p hgi s as i m p l eg r a p ho fo r d e r 胛ag r a p h o fo r d e r i s 。a l l e d d a n c y c l i c i fi tc o m a i n sc y c l e so fe v e r yl e n g t ht , 3 z 玎，a n d i sc a l l e dw e a k l y p a n c y c l i ci fi tc o n t a i n sc y c l e so f a l ll e n g t h sb e t w e e ni t sg i r t ha n dc i r c u m f e r e n c e t o d a i l c y c l i cg r a p h s ，b o n d y ( 1 9 7 1 ) p r o v e s ac l a s s i ct h e o r e mt h a te v e r yh a m i l t o m “ g r a p ho f o r d e r 刀a n ds i z ee x c e e d i n g ”么i sp a n c y c l i co rc o m p l e t e b i p a r t i t e t h e n , b r a n d t ( 19 9 7 ) e x t e n d sb o n d y st h e o r e m , a n dp r o v e s t h a te v e r yn o n - b i p a r t i t eg r a p h o f o r d e r 挖孤ds i z eg r e a t e rt h a n ( 肛l 么+ 1 i sw e a k l yp a n c y c l i c ，a n dc o n j e c t u r e s t h a te v e r yn o n b i p a r t i t eg r a p ho f o r d e r ”a n ds i z ea tl e a s t 吆j - n + si s w e a k l y p a n c y c l i c a n dt h e nb o l l 0 6 sa n dt h o m a s o n ( 1 9 9 9 ) a l m o s tp r o v e st h i sc o n j e c t u eb y l ， e s t a b l i s h i n gt h a te v e r yg r a p h o fo r d e rna n ds i z ea tl e a s t p 石j 一 + 5 9 i sw e a k l y p a n c y c l i c o rb i p a r t i t e i nt h i sp a p e r , w es h o wb r a n d t sc o n j e c t u r e i st r u ef o r t r i a n g l e f r e eg r a p h s ，t h a te v e r yn o n - b i p a r t i t e t r i a n g l e - f r e eg r a p h o fo r d e r 玎a n ds i z e a tl e a s t 吆j 一 十5i sw e a k l yp a n c y c h c k e y w o r d s ： w e a k l yp a n c y l i c t r i a n g l e - f r e en o n - b i p a r t i t e 硕士学位论文 m a s t e r st h e s l s 无三角形的弱泛圈图 1 介绍 本文仅考虑无环和无重边的有限无向图。对于图g 的点z ，用n 。( x ) 表示x 在g 中的邻域，x 在g 中的次用如( 砷= j o ( 蚓表示。设h 是图g 的子图， x 矿( g ) 一矿( ) ，我们同样用( x ) = 。( x ) n 矿( ) ，d 。 ) = l n 。( x 表示x 在h 中邻域和次。设s v ( g ) ，用g s 表示由g 关于j 的导出子图，并令 g s = c v ( g ) 一s 。此外。我们分别用p ( g ) ，5 ( c ) ，c ( g ) 和g ( g ) 表示图g 的边 数，最小次，周长( 最长圈的长度) 和围长( 最短圈的长度) 。文中未加说明 的概念和符号见文献 7 。 由关于十二面体的个数学游戏而起源的h a m i l t o n i a n 图问题( 1 8 5 6 ) ，经历 一百多年，于上世纪五十年代后，吸引了大批图论专家的兴趣，对它的研究从 此步入了繁荣时期。从d i r a c ( 1 9 5 2 ) 给出h a m i l t o n i a n 图的一个充分条件：设g 是 最小次为占的胛阶图，其中艿芸， 3 ，则g 含有h a m i l t o n i a n 圈。之后，许 2 多关于h a m i l t o n a i n 图性质的经典定理陆续被证b 珥 1 0 。在此期间，通过边参数 研究h a m i l t o n i a n 图性质方面也取得重大进展。 设g 是玎阶图，如果对于任意的整数，：3 ，胛，g 中含有长度为1 的 圈，则称g 为泛圈图。关于泛圈图，b o n d y 证明了下述经典结论。 定理1 ：( b a n d y 2 ) 每个边数至少是h _ 2 的刀阶h a m i l t 。n i a n 图是泛圈图或完全 二部图。 硕士学位论文 m a s t e r st h e s i s 后来，h g t g g k v i s t ，f a u d r e e 和s c h e l p 改进了b o n d y 的定理。 定理2 ：( h j t g g k v i s t ，f a u d r e e 和s c h e l p 4 】) ，每个边数至少是生二；e + 1 的 阶 h a m i l t o n i a n 图是泛圈图或完全二部图。 在文献【3 】中b r a n d t 去掉了图的h a m i l t o n i a n 性，定义图的弱泛圈性：图g 称 为弱泛圈的，如果g 含有长度为f 的所有圈，其中g ( g ) z c ( g ) 。同时他推 广了定理2 ，证明了下面定理。 定理3 ：( b r a n d t l 3 ) 设g 是”阶非二部图，其边数至少为竺二竖+ l ，则g 是 q 弱泛圈的。 更进一步，b r a n d t 3 提出了下面更强的猜想。 猜想1 ：( b r a l d t 【3 ) 设g 是力阶图，其边数至少为塑二丛! ! 翌+ 4 ，则g 是弱 泛圈图或二部图。 说明b r a n d t 猜想不能再加强的例子是下面两类图。一类是完全二部图 k 。n ，另一类是由一个完全二部图k k 。和一个c 4 组成，其中c 4 与二部图中 点数多的分部有相邻的两个公共点。 对于猜想1 的重要进展要归功于b o l l o b d s 和t h o m a s o n 。 定理4 t ( b o l l o b 6 s 和t h o m a s o n 1 ) 设图g 是 阶非二部图，如果g 边数至少为 1 等) 一”+ 5 9 ，则图g 含有长度为，的所有圈，其中4 ，c ( g ) 。 虽然定理4 的边数比定理3 中少大约昙条，但其证明却复杂得多。 在本文中，我们将证明对无三角形的图，猜想1 是正确的。 定理5 ：设图g 是胛阶无三角形的非二部图，如果g 边数至少为f 竺i - - n + 5 ， 硕士学位论文 m a s t e r st h e s i s 则图g 含有长度为，的所有圈，其中4 蔓l c ( g ) 。 2 定理5 证明的概述 设图g 是定理5 的极小反例，我们通过证明g 的一些性质来说明这样的图g 是不存在的，易知： ( 21 ) 占( g ) 2 ； 由定理s 碍l n 等- - n + 5 l 华j + 2 ，携 ( 22 ) ”7 ： ( 2 3 ) 图g 有4 一圈。 假设( 23 ) 不成立，又聆7 ，于是 当”= 7 时，因为g 无三角形，且无4 一圈，则有 若g 的最小圈是5 - - 圈c ，设( x ，y ) = g c 。，则x ，y 均至多与圈上一点相连， 于是 p ( g ) = 8 ( g 【c 】) + 如( z ) + d c c v ) + j e ( g ) n ( 砂l 5 + 2 + 1 = 8 这与啊，倒s 划，矛盾 若g 的最小圈是6 一圈时c ：，设 z ) = g c ：， 因为g 无三角形，且无4 一圈，则：至多与c ：上一点相连， 于是 e c g ，e c g c c ：，+ 如：c z ，6 + = ，这与e c g ，l 等j 一即+ s = t 。， 矛盾 所以，? 7 ， 于是门8 ，又g 不含有4 一圈，由 8 定理1 2 ，则有 1 3 = l 等卜+ 5 三( 1 + 丽) - 2 ( 1 + 历) ，矛盾 所以( 23 ) 成立。 姗m 如籼班引一c l 华卜棚 账次点。显 然，如果x 是低次点，则g x 有足够多的边满足定理要求，。于是g x 是弱泛 圈图或二部图。若点x 不是低次点，则称z 为高次点。注意到： m ，忖聆一屯引m 曲，2k - l , 当n = 2 k ：+ 1 ，于是 ( 24 ) x 是低次点当且仅当d ( x ) 罢一i 。 定理5 的证明思路是：首先证明定理5 的极小反例g 的周长至少是一1 ) ， 然后证明如果图g 有( 蚪一1 ) 一圈，则图g 是弱泛圈的。最后证明如果图g 是 h a m i l t o n i a n 图，则图g 有一1 ) 一圈。上述三个结论说明定理5 的极小反例g 不存在，于是定理5 成立 3 极小反例的周长 设图g 是极小反例，c 是g 的最长圈，我们首先证明高次点的一些性质。 ( 31 ) 设x ，y 是图g 的两个不同的高次点。如果x ，y 仨v ( c ) ，则x ，y 畦e ( g ) 假设( 31 ) 不成立，如果。( x ) n ：o ) m ，设n c ) n ；( y ) ，则 圈x u c u y x 比c 长， 矛盾，于是n c ( x ) n ； ) = 中 同理c o ) 九昵( x ) = 中， 因为图g 是无三角形的， 4 硕士学位论文 m a s t e r st h e s i s 于是 n o ( y ) n n 。( y ) = n c ( x ) n ；( x ) = n c o ) n ；( y ) = 中 所以。( 如；( z ) ，n c ( y ) 和；( y ) 是两两不相交的点集，则有 2 ( d e ( x ) + d c ) ) 矿( c ) l 由图g 是无三角形，则如一。( + d 。一。( y ) - v ( g c ) i ， 于是 撕m 捌掣们_ c ) f 一粤， 这与x ，y 均是高次点矛盾，于是结论成立。 下面，用巧和分别表示矿( g ) 矿( c ) 的低次点集和高次点集 ( 32 ) 如果c ( g ) ”一2 ，则c 外至少有一个低次点， 即矿中 用反证法，设c ( g ) 聍一2 ，且巧= 中，则g c 的每个点均是高次点。 设z 是g c 的任意一点，由( 31 ) 知，。一。( x ) = 巾， 又c 是图g 的最长圈，则 n c ) n ：( x ) = 中于是 撕，= 撕，s 粤孚 悼卜孚 _ 1 m 所以g x y 是连通图或有两个分支，其中个是个独立点v 对于后一种情况： 由占( g ) 2 ，v 征c ，则v 必与y ，y 相连，而且x ，j ，均与g 一 x ，y ，1 0 的一个分部 若x 和y 均与g 一 x ，y ，v ) 同一分部相连时，则 x y e ( g ) ，否则g 是二部图，y v 与x ，y 相连，于是v ，x ，y 组成三角形 所以x ，y 分别与g 一 z ，y ，嵋不同分部相连 j a g 一 x ，y ，v ) 构造g 。：增加一个新点w 与x ，y 所有邻点相连，于是 邸冲啦”小降h 斜：一靶部图 所以g 。是弱泛圈图， 又由c g ，则g 含有d c 卜1 ) 一圈，且此圈必含有w 硕士学位论文 m a s t e r st h e s i s 于是在g 中，用x w 代替w ，得到g 中( j c l + 1 ) 一圈， 矛盾 所以，如果x ，j ，是g c 的两个低次点，则g x y 是连通图， 于是 x 和j ，与g z y 同一分部相连，且x y e ( g ) ，否则，g 是二部图 从而y 是x 在g x 的分部中的唯一邻点。于是 ( 33 ) 如果x ，y g c 且是低次点，n g x y 是连通图，r y 是z 在g x 的 分部中的唯一邻点。 因为图g 无三角形，有( 33 ) 知，g c 中至多有两个低次点，即 ( 34 ) 1 7 l 2 ( 3 5 ) 圪= m 假设( 35 ) 不成立，则存在一点m 圪 又由( 3 2 ) 知，k 。， 于是j c = 刀一k i + l 吒| ) n 一2 因为c 是图g 的最长圈，则有如( m ) 掣， 于是 d o _ c ( 巾= 蛐m ( 掣， y i - - j 亨n ，因为图g 无三角形，r e 自( 31 ) 和( 33 ) ，则有 叱一c ( y 1 ) = d 屹 1 ) + d r , ( y 1 ) 1 于是撕1 ) - 掣，= 1 ，从而i q 狲3 设p = m y ：m 是g c 的最长m 一路，则有2 f 3 硕士学位论文 m a s t e r st h e s i s 因为图g 无三角形，于是如一。) = 1 又占( g ) 2 ，则有c o ，) 由，不妨设“c o ，) 因为c 是图g 的最长圈，于是 n c ( y 1 ) n ( “一，”一，”+ ，“+ + ) = ，n c ( y 】) n n c ( y 1 ) = 中 所以如o ，) i c l 2 - _ _ 2 3 ，这与噍( m ) = 粤矛盾， 所以( 35 ) 成立。 n ( 3 4 ) n ( 3 5 ) 有，l v ( g c ) i 2 ，于是l v ( g c ) l = 防i = 2 设k = x ，y ) ，则有x y e ( g ) f 1 g x y 是h a m i l t o n i a n 的二部图 设k 和是g - - x - - y 的两个分部，且y 与k 中点相邻 由( 33 ) 知，y 是r 在k w y ) 中的唯一邻点 同理，x 是y 在吃u ( x ) 中的唯一邻点 又e ( g ) l 鲁j - n + 5 ：, 矿1 2 + 。，由引理t 知，g 含有c z 吲+ ，) 一圈，矛盾 所以c ( g 1 一一1 4 含有一1 ) 一圈的图 本节中，我们通过假设极小反例g 含有0 1 ) 一圈而导出矛盾。 引理8 ：设图片是阶为2 k + 1 的h a m i l t o n i a n 图，其边数至少为k2 一七十4 ，含有 一点x 满足日一x 是二部图，则图日含有长度为2 l + 1 的所有奇圈， 其中2 兰i k c 证明：用反证法，假设日是引理3 的极小反例，不妨设日不舍某个( 到+ 1 ) 一 圈，其中2 茎，七一1 。 设c = y v l v 2 v 2 k - 1 1 ，2 女是h 的h a m i l t o n i a n 圈，显然k 3 ( 41 )，2 ； 假设( 41 ) 不成立，则图月不含5 一圈， 则 对于f ：1 i 2 k 一3 ，v 。和v m n 少n - - a n x 不相连， 于是 2 如( x ) 一d = i n ( x ) r 、 v 】， 其中d = 1 。( x ) n v 。，v ：，如，v 2 k - 2 ，v 2 k - l ，v ”) 1 所以州啦+ l 竿l l 2 j 用k ，表示h r 的两个分部，其中u v 对于口( x ) ，b n ( x ) ，定义a = i t ( d ) 、 6 ) ，b = h ( 6 ) 口) 钺= 七凳蚰饵 选择这样的d ，b ，使得血n h ，俐) 1 ( 例如，取盘= u ，b = v ：。) ，因为h 没 有5 一圈，所以h 中没有从4 到b 的边，于是 e ( 日一x ) s k 2 一 4 l x l b l i k u 凸) | 一l k ( 爿u ( 6 ) ) l s 。 = ( 七2 2 k + 3 ) 一d 彳l 一0 ( b i - 0 - 又d h ( x ) s 尼+ ! ；，于是 硕士学位论文 m & s t e p , st h e s i s 妇h k 2 - k + 3 ，1 字卜，贿l 字卜 特别，当占女= 0 时，d 5 ，于是l “，v ：h ，v ，v 2 k ) n 日( 功i 3 因为h 没有5 一圈，则i 1 1 ；：h 和v 3 v 2 均不是的边 取( 盘，b ) = ( v ，v 2 。) 或( v 3 ，v 2 。) ， 则有 a n h ( r ) ，b n ( x ) ，且g a b = 1 ， 于是 d 7 ，这与d ：i n h ( x ) n v l ，v 2 ，v 3 ，1 ，2 ，v ：，v 2 k ) | 矛盾 ( 4 2 ) d n ( y ) 2 k 一3 假设( 4 2 ) 不成立，则有d n ( x ) 2 k ，2 4 d + = i n h ( z ) n ( q ，2 - v 2 1 - 1 ) u ( v v ：。1 2 k - 2 1 + 2 ) l 因为不含( 2 ，+ 1 ) 一圈，用类似( 4 1 ) 的证明可得 2 k 一2 1 + 1 2 d h ( z ) 一d = ( x ) n ( v ，1 i + 2 1 - 1 牡2 k 一2 1 + 1 又d 。2 ( 2 l 一1 ) = 4 1 2 ，2 ，k 一1 ，贝0 有 d h ( z ) k + ，一1 2 k 一2 ， 又如( x ) 2 k 一2 于是 如( x ) = 2 k 一2 ，且，= k 一1 ，所以。( z ) = 矿( c ) ( z ，v ：。，v ，) 此时圈c = x v 2 v 3 1 2 k - 1 x 是( 2 ，+ 1 ) 一圈，矛盾 于是( 4 2 ) 成立。 由( 4 2 ) ，贝4 有e ( h x ) ( t 一1 ) 2 一( 七一1 ) + 5 由h 一 x ，v ，v ：。) 构造h ：增加一个新点z 1 ，与v 1 和v 2 k 的所有邻点相连，则 日是阶为2 一1 的h a m i i t o n i a n 图，且胃。一x 1 是二部图， 又e ( h ) p ( 日一x ) 一i e ( 何) n f v ，v ：。) i 一1 ) 2 一( 露一1 ) + 4 由3 蔓，t l 和月的极小性可知：日含有长度为2 ，一1 的奇圈。 设c ，d 是此圈上x + 的两个相继点，且c 与v ：。是在h 一( z ) 的同一分部中， 用“，x v 2 。d 代替“d ，则得到月中的( 2 ，+ 1 ) 一圈， 矛盾 所以结论成立。 为了证明本节的主要结论，需要引用下面两个引理。 引理4 ：( b o l l o b d s 和t h o m s o n ( 1 ，引理9 ) ) 设日是阶为2 女+ 1 的非二部图，其边 数至少为k2 一k + 4 ，含有一点z 满足h r 是h a m i l t o n i a n 的二部图，则胃是 h a m i l t o n i a n 图。 引理5 ：( b o l l o b d s 和t h o m s o n ( t ，引理8 ) ) 设h 是阶为2 七的h a m i l t o n i a n 的二 部图，其边数至少为丛笔坐，则日含有长度为2 z + 2 的所有偶圈，其中 i ，豇一1 。 下面证明定理5 的极小反倒不含有印一1 ) 一圈。 引理6 ；设图g 是定理5 的极小反例，则g 没有m 1 ) 一圈。 证明；假设极小反例g 有伽一1 ) 一圈c ，x 是c 外的一点，因为g 无三角形，则 有 ( 4 3 ) c 0 ) 是g 上的独立集 ( 4 4 ) x 不是高次点 假设( 4 4 ) 不成立，则如( r ) = d o ( x ) 芝 由c 4 ，可知掣 l 孚j ，于是开是奇数，令”= z 七+ ，则如c x ，= 后 由( 4 3 ) ，不放设c = c l c 2 c 2 c 1 ，n c o ) = b ，c 3 c 2 l - 1 ) 显然，g 含有所有的偶圈2 1 ，其中2 z k 因为图g 不是二部图，于是c 必有偶数长的弦， 由( 4 3 ) ，不妨设此弦为c 2 j c ：，其中i ，一是整数，且1 f 掣掣 硕士学位论文 m a s t e r st h e s i s 由引理5 知，g y 含有长度为2 ，的所有偶圈，其中2 ，k 从而g 含有长度为2 ，的所有偶圈，其中2 ，k 所以g 是弱泛圈，矛盾 于是结论成立。 5 t t a r a i l t o n i a n 图 在本节中，我们考虑h a m i l t o n i a n 图。如果图g 是定理5 的极小反例，且 是h a m i l t o n i a n 图，则图g 有函一1 ) 一圈。证明思路：先找一个仍一2 ) 一圈，然 后扩充，产生( v t 一1 ) 一圈。 设昱是玎阶图，它中的积一2 ) 一圈c 称为特别的，如果满足条件：不在c 上 的两点x ，y ，有砂e f f - o ，且如( x ) + 幽( y ) 押一3 。 为了证明下面的主要引理，需要引用s c h m e i c h e l 和h a k i m i 的圈结构定理： 定理6 ：( s c h m e i c h e i 和h a k i m i 6 ) 设图日有h a m i l t o n i a n 圈c = 1 - ，i v 2 v 。v 1 ， 设d 。( v 1 ) + d h ( v 。) 刀，贝： ( i ) h 是泛圈图，或者： ( i i ) h 是二部图，或者； ( i i i ) 除了n - 1 ) 一圈外，h 含有所有长度的圈： 而且，如果( i i i ) 成立，则如( v - 2 ) ，如( v 。) ，如( v ：) ，如( v ，) 昙，且图h 在 v 1 v 。附近有两种可能构形。第种构形是：点v n - 2 ，l ，n _ 1 ，v 。，v ，v ：，v 。 除了圈c 上的边相连外，是独立的，并且v 。v 。，v n y n _ 4 * v l v 。，v 。1 e ( g ) ( 如 硕士学位论文 m a s t e r st h e s i s 图) ；另一种构形是，除了v n v 3 e ( g ) 和v l v ，仨目r g ) 外，与第一种构形相同( 当 d ( v 1 ) ( ”6 ) ( n - 1 1 【) + 1 0 = n 2 - 1 7 n + 7 6 = ( 打一争2 + 萼，矛 盾 所以订是偶数，此时占：0 又由( 55 ) 有：p 一8 ) o - 8 ) + 1 2 0 ， 又r 胛，且月7 ， 则有， 8 2 0 矛盾 所以结论成立。 y 面我q j i i e n ，如果图g 是无三角形的，且有特别的一2 ) 一圈，则图g 有 m 一1 ) 一圈。 引理8 ：y 殴 n g 是定理5 的极小反例，a b e ( g ) ，且如( 口) + d 。( 6 ) ”一3 ，假 设由点集矿( g ) 一 口，6 ) 所导出的子图是h a m i l t o n i a n 图，但非二部图，则图g g 印一1 ) 一圈。 证明：假设图g 没有( n - 1 ) 一圈，设c 是g 一枷，n - - + ( 7 7 2 ) 一圈。 令a 2 c ) ，b = n 。( 6 ) ， 不妨设f a f 蚓 n y i n g 无三角形， 于是a n b = 中，a 和b 都是图g 的独立集， r n y 口n g 没有0 1 ) 一圈，则a + 也是独立集。 如果爿u 彳+ = 矿( c ) ，则g 一 d ，辨是二部图，矛盾 于是i a i _ n - - 2 如果a o ( 口) + 如( 6 ) 胛一l ，则h 十例2 月一3 ，于是川2 旦善 又由h 阳一5 ，则有川昙一2 ， 如果4 是由红色点组成，则a 包含至多除掉某个红点的其他所有红点， 因为图g 没有0 1 ) 一圈，于是a “n 占= 中 所以b 中点全部是蓝点，于是图g 是二部图，矛盾 所以l a l = 昙一2 ， 又因为彳n 4 + = 中 于是a 中点由红，蓝两色点分成两段。 不妨设c = v l v 2 v 2 k v i ，a = “，v 2 v 2 l 。) u v 2 m ，v 2 v m 2 ) ， 其中，是a 中红色点的个数。 由a n b = a ”n b = a n b = 中，于是 硕士学位论文 m a s t e r st h e s i s b n 即u v 2 ，v 2 ，v 2 ， j a l + 1 8 i l c i 一4 = 刀一6 ， 所以结论成立。 v ：。) ) = 中， 所以 与l a i + 俐胛一5 矛盾 6 定理5 的证明 利用前面我们所证明的诸多引理，现在可以证明定理5 。 定理5 ：设图g 是”阶无三角形的非二部图，如果g 边数至少为l 生- n + 5 ， l4j 则图g 含有长度为，的所有圈，其中4 ，c ( 0 ) 。 证明：设图g 是定理5 的极小反例，由引理2 知，图g 有0 1 ) 一圈或”一圈。 如果图g 有胛一圈，由引理7 ，引理8 ，引理9 知，图g 有铆一1 ) 一圈。 于是图g 必有印一1 ) 一圈，而这与引理6 矛盾， 所以极小反例不存在，于是 所以g 含有每个长度为，的圈，其中4 ，c ( g 1 。 硕士学位论文 m a s t e r st h e s i s 参考文献： 1 bb o l l o b 6 sa n da t h m o a s o n w e a k l yp a n c y c t i cg r a p h s j c o m b i nt h e o r ys e t b 7 7 ( 1 9 9 9 ) ，1 2 1 1 3 7 。 1 2 】j a b o n d y p a n c y c l i cg r a p h s ，jc o m b i n ，t h e o r ys e r b 1 1 ( 1 9 8 1 ) ，8 0 一8 4 。 f 3 1 s b r a n d t as u f f i c i e n tc o n d i t i o nf o ra l ls h o r tc y c l e s ，d i s c r e t ea p p l e m a t h 7 9 ( 1 9 9 7 ) ，6 3 - - 6 6 。 【4 lr ，h 蕴g g k v i s t ，rt f a u d r e e ，a n dr h s c h e l p ，p a n c y c l i c g r a p h s c o n n e c t e d r a m s e yn u m b e r ， a r s c o m b i n ，11 ( 1 9 8 1 ) ，3 7 4 9 。 【5 1 j m i t c h e ma n de ，s c h m e i c h e l p a n c y c l i ca n db i p a n c y c l i cg r a p h s - - as u r v e y , i n o r a p h sa n da p p l i c a t i o n s ，p r e c e e d i n go ft h ef i r s tc o l o r a d os y m p o s i u mo