（运筹学与控制论专业论文）图的泛圈性和点泛圈性.pdf

摘要 哈密尔顿问题在十八世纪五十年代由w i m 锄r o w a nh a m i l t o n 提出在1 9 7 1 年。b o n d y 在【n 1 中提出除了一部分特殊的图类外，如果一个图是哈密尔顿的蕴涵了这个图也 是泛图图随后人们给出了许多关于图的泛圈性的定理。同时，人们也开始关注图的 点泛圈性因为由点泛固性可以推出泛圈性，同样泛圈性也可以推出哈密尔颁性 在f 2 9 】中，作者给出定理：设g 是一个n 阶二连通图，且6 ( g ) 2t ，若对g 中的任意两个不相邻的点 和t ，有i n ( u ) u ( ) i n t ，那么g 是一个泛圈图 或7 1 , = 2 t ，g 型甄在这篇论文中我们考虑将这个条件减弱到只考虑图中距离为2 的点时。于是得到了泛圈图的一个充分条件：若对g 中的任意距离为2 的点u 和t ， 有i n ( u ) u ( t ，) i t l 一6 ，那z , g 是一个泛圈图或g 是以下情况之一：( 1 ) g 是一 个5 圈，( 2 ) g 鲁磁2 在【3 】中，有如下定理：设g 是一个l 阶图，f l 3 且观之4 吖3 1 1 ，那么g 中的每个点都含在一个3 圈中类似上面结论，我们也只考虑图申距离为2 的点对。 得到下面结论：若对g 中的任意距离为2 的点u 和钞有d ( u ) + d ( t ，) f 警1 1 ，那 么g 中的每个点都舍在一个3 圈中 另外。文章中还给出了两个结论的详细证明在最后一章中，我们提出了一些在 今后的研究中可以思考的问题 关键词：2 一连通图；泛圈图：点泛圈图；最小度 v ab s t r a c t t h eh a m i l t o n i a np r o b l e mn a m e df o rs i rw i l l i a mr o w i i l lh a m i l t o n 咖t r a c ei t so r i g i n 8 t ot h e1 8 5 0 8 i n1 9 7 1b o n d y 【1 1 1p o s e dt h a tt h eg r a p hw a sh a m i l t o n i a na l s oi m p l i e s t h a ti tw a sp a n c y c l i ef e x c e p tf o rm a y b eas i m p l ef a m i l yo fe x c e p t i o n a lg r a p h 8 ) m a n y t h e o r e m sa b o u tp a n e y c l i c i t yw e r eg i v e ni nt h ef o l l o w i n gy e a r s m e a n w h i l e ，t h es u l i - c i e n te o n d i t i o me v e nf o rv e r t e xp a n e y c l i e i t yw e r ee x a m i n e d ，s i n c ev e r t e xp a n e y e l i e i t y i m p l i e sp a n e y e l i c i t ya n dp a n e y e l i c i t yi m p l i e sh a m i l t o n i e i t y i nf 2 9 】，t h ea u t h o rg a v et h a tl e tgb ea2 - c o n n e c t e dg r a p h 丽t ho r d e rt la n d 6 ( a ) t ，i fi ( t ) u 扣) i n tf o ra n yn o n a d j a c e n tv e r t i c e s 牡a n dt ，i ng ，t h e n gi sp a n e y e l i eo r l = 2 t ，g 型玩i nt h i st h e s i sw ee o m i d e rt or e l a xt h eh y p o t h e s i s t oj u 或t i c ko v e rt h ev e r t i c e sm t hd i s t a n c e2a n dw eo b t a i nas u f f i c i e n tc o n d i t i o n f o rp a n e y c l i eg r a p h s l e tgb e8 参o l n e c t e dg r a p hw i t hnv e r t i e 蚂i ff o ra n yt w o v e r t i c e s 让，t ，i n g 而t h d ( t ，) = 2 w e h a v e l ( u ) u ( ”) i n - 5 ，t h e n g i s p 柚e y e l i c o l rgi si s o m o r p h i ct oo i l eo ft h ef o l l o w i n g s ：( 1 ) gj 88 铀y e l e ，( 2 ) g 岂k g ，； i n 【3 】，w e h a v e t h a t l e t g b e a g r a p h o f o r d e r n 3 舢c l l t h a t 观f 4 n 3 1 - 1 ，t h e n e v e r yv e r t e xo fg j 8e o n t 流i n e di n83 - c y c l e l i k et h ea b o v er e s u l t a n yt w ov ：e r t i e e s w h i c ha r eo fd i s t a n c e2i 8d i s c i l 8 s e d t h e nw eo b t a i nt h ef o l l 硎n gr e s u l ti nt i mt h e s i s ： l e t g b ea g r a p ho f o r d e r 竹23s u c h t h a t d ( t ) + d 扣) f 警1 一1 w h e r ed ( u ， ) 宣2 i ng t h e ne v e r yv e r t e xo fgi se o n t 血e di na3 - c y c l e w h a t sl l l o l l e ，d 删l e dp 触o ft h et w or e s u l t sa r ep r e s e n t e d i nt h el a s tc h a p t e r ， w eg i v e 鲫e r a li n t e r e s t i n gt o p i c sl b rf u r t h e rw o r k m k e y w o r d s ：2 - c o n n e c t e dg r a p h ；p a n c y c l i cg r a p h ；v e r t e xp a n c y c l i cg r a p h ；m i n i m u m d e g r e e a c k n o w l e d g e m e n t s 1w o u l dl i k et ot h a n kp r o f e s s o rz h i r e ns u n , m ys u p e r v i s o r ，f o rh i sm a n ys u g g e s t i o n s a n dc o n s t a n ts u p p o r td u r i n gt h i sr e s e a r c h h ei n t r o d u c e dm ei n t ot h er e s e a r c ho ft h e g r a p ht h e o r ya n dg a v em ee n o r m o u sh e l pd u r i n gc l a e st i m ea n da f t e rs c h 0 0 1 ia ma l s ot h a n k f u lt op r o f e s s o rb 口凹帆9x u , p r o f e s s o rx i n g h ez b t p r o f e s s o r x u e b i nz h a n g , p r o f e s s o rx i n p i n g a n dp r o f e s s o rs h i t a if u t h e y 眦w o n d e r f u l p e o p l ea n dt h e i rc o u r s 铝m a k er e s e a r c hl i k et h i sp o s s i b l e ih a v et h ep l e a s u r eo fm e e t i n gp r o f e s s o rf u t a iz h a n g f r o mh i sc l a s s ik n o wt h e a p p l i c a t i o no ft h eg r a p ht h e o r yi nt h en e t w o r ks e c u r i t y is h o u l da l s ot h a n kt e a d h 懿 t h a tm u g h tm ei nn a n j i n gn o r m a lu n i v e r s i t yi nt h ep a s t3y e a r s o fc o u r 鼬，ia mg r a t e f u lt om yp a r e n t sa n dx i n y ih u a n g ，f o rt h e i rp a t i e n c ea n d o v e 。w i t h o u tt h e mt h i sw o r kw o u l dn e v e rh a v ec o m ei n t oo x i 8 t e n c e ( 1 i t e r a l l y ) f i n a l l y , 1w i s ht ot h a n k t h ef o l l o w i n g ：z h i r uq i ，x i n h u ay u a n ，h a i y a ny a n g ，f e n g p a n ，x i n o x ul ua n dw e n l i a n gt a n g ( f o rw eo f t e nd i s c u s ss o m ep r o b l e m st o g e t h e r ) ； y u l a nz h a n g ，q i a nx ua n do t h e r si nt h en o 1 2d o r m i t o r yb u i l d i n g ( f o ra l lt h eg o o d a n db a dt i m e sw eh a dt o g e t h e r ) ；y iy a o ，x u e y u n nt a n ，m h u ns u n ，n a nd a la n d c h e n gz h u ( f o rt h e i rh e l p sd u r i n gt h e s et h r e ey e a 腮) n a n j i n gj i a n g s u ，p e o p l e 8r e p u b l i co fc h i n a m a r c h1 5 ，2 0 0 6 腑，黝j c h a p t e r1 p r e l i m i n a r i e s t h eh a m i l t o n i a np r o b l e mi sg e n e r a h yc o n s i d e r e dt ob ed e t e r m i n i n g c o n d i t i o n su n d e rw h i c hag r a p hc o n t a i n sas p a n n i n gc y c l e n a m e df o r s i rw i l l i a mr o w a nh a m i l t o n ，t h i sp r o b l e mt r a c e si t so r i g i n st ot h e 1 8 5 0 s t o d a y , h o w e v e r ，t h ec o n s t a n ts t r e a mo fr e s u l t si nt h i sa r e a c o n t i n u e st os u p p l yu sw i t hn e wa n di n t e r e s t i n gt h e o r e m sa n d8 t m f u r t h e rq u e s t i o n s “ 1 1d e f i n i t i o n sa n dn o t a t i o n s d e f i n i t i o n1ag r a p hgi sa no r d e r e dt r i p l e ( y ( g ) ，e ( g ) ， 惦) c d 7 扣 s i s t i n go y 口n o n e m p t ys 酣v ( c ) o yv e r t i c e s , ns e te ( g ) ，d i s j o i n tf r o m y ( g ) ，巧e d g e s ，a n da ni n c i d e n tf u n c t i o n 怕t h a ta s s o c i a t e sw i t he a c h e d g eo yg a nu n o r d e r e dp a i ro | n o tn e c e s s a r i l yd i s t i n c t ) v e r t i c e so yg d e f i n i t i o n2ag r a p hi ss i m p l e 矿i th a sn ol o o p sa n dn ot w oo i 伽 1 l i n k sj o 轨t h es a m ep a i ro lv e r t i c e s t h r o u g h o u tt h i st h e s i sw ec o n s i d e rf i n i t es i m p l eg r a p hg = ( ke ) ， u n l e s so t h e r w i s ei n d i c a t e d d e f i n i t i o n3t h en u m b e ro fe d 9 7 e s 盯t h eg r a p hgi so f t e nc a l l e dt h e s i z eo f g d e f i n i t i o n4t h ed e g r e ed 矿o av e r t e xui ngi st h en u m b e ro fe d g e s o ，gi n c i d e n t 埘忱t ， w ed e n o t eb y6a n d t h em i n i m u ma n dm a x i m u md e g r e e s r e s p e c - t i v e l y , o fv e r t i c e so fg d e f i n i t i o n5ab i p a r t i t eg r a p hi so n ew h o s ev e r t e xs e tc a nb ep a r t i - t i o n e di n t ot w os u b s e t sxa n dys u c ht h a te a c he d g eh a so n ee n d 饥 xa n do n ee n d 讥y ac o m p l e t eb i p a r t i t eg r a p hi sas i m p l eb i p a r t i t e g r a p hw i t hb i p a r t i t i o n ( x ，y ) 伽w h i c he a c hv e r t e xo xi sj o i n e dt oa n y v e r t e xo f y d e f i n i t i o n6t h es e to fa l ln e i g h b o r so yav e r t e x $ y ( g ) i sd e n o t e d b y ( z ) = r g ) i f aa n db 口他s u b g r a p h so f go rs u b s e t so y 【g ) ， w ed e f i n e 裔 ) = n ( z ) n ba n d v b ( a ) = n ( a ) n b c l e a r l y , d ( 第) = j ( z ) ia n dd b ( z ) = l b ( z ) 1 2 d e f i n i t i o n 气as u b s e tso fvi sc a l l e da ni n d e p e n d e n ts e to f g 毽 n ot w ov e r t i c e so fsa r ea d j a c e n t 讥g t h en u m b e ro fv e r t i c e s 轨a m a x i m u mi n d e p e n d e n ts e to fgi sc a l l e dt h ei n d e p e n d e n tn u m b e r9 lg a n di sd e n o t e db y ( g ) d e f i n e 七 o k ( a ) = = r a i n z i = 1 w h e r ek a ( g ) d g ( v i ) ： v l ，v 2 ，) i sa ni n d e p e n d e n ts e to fg ) ， d e f i n i t i o n8ac y c l eo fag r a p hi sas u b s e to ft h ee d g es e tt h a tf o 7 l 善a p a t hs u c ht h a tt h ef i r s tn o d eo ft h ep a t hc o r r e s p o n d st ot h el a s t ac y c l e o fl e n g t h 后i sc a l l e dk - c y c l e t h eg i r t ho fgi st h el e n g t ho yas h o r t e s t c y c l e 讥ga n dt h ec i r c u m f e r e n c ei st h el e n g t ho fal o n g e s tc y c l ei ng d e n o t e db yg ( c ) a n d c ( g ) ，r e s p e c t i v e l y d e f i n i t i o n9a ne d g ex yge ( c ) w i t hz ，y v ( c ) i sc a l l e dac h o r d o lc d e f i n i t i o n1 0 聪ci s8c y c & o i g 。柚ed e n o t eb y - 0t h ec y c l ew i t h 伍 g i v e no r i e n t a t i o n 盯u y ( c ) ，t h e nt 上+ d e n o t e st 九e8 u c c e s s o ro f 缸o n 刁a n d “一i t sp r e d e c e s s o r ；t 正+ 2 = ( t 广) + ，e t c d e f i n i t i o n1 1ah a m i l t o nc y c l eo fg i s 口c y c l et h a tc o n t a i n se v e r y v e r t e xo fg ag r a p hi sh a m i i t o n i a n 讨i tc o n t a i n sah a m i l t o n c y c l e d e f i n i t i o n1 2gi sh a m i l t o n c o n n e c t e d 矿e v e r yt w ov e r t i c e so fg a r e c o n n e c t e db yah a m i l t o np a t h 3 ：兰二一丝型堡坐垒塑塑丝兰绁 d e f i n i t i o n1 3t h ec l o s u r eo ya o fo r d e rn i st h eg r a p ho b t a i n e d f r o m g b yr e c u r s i v e l yj o i n i n gp a i r so fn o n a d j a c e n tv e r t i c e sw h o s e 咖舰s 啪 诂耐鼬几u n t i ln os u c hp a i rr e m a i n s w ed e n o t et h ec l o s u r e0 1 a b ! ， c f ( g ) l e tgb aag r a p ho fo r d e r 几 d e f i n i t i o n1 4ag r a p hg 妇c a l l e d p a n c y c t i c 矿靠c o n t a i n s 口c y c l eo f l e n g t hkf o re v e r yi n t e g e rkw i t h3 k n d e f i n i t i o n1 5a g r a p hi sc a l l e dv e r t e xp a n c y c l i ci fe v e r yv e r t e xi sc 0 7 1 , - t a i n e d 讥ac y c l eo f l e n g t hk f o re v e r yi n t e g e r 惫w t h3s 磨s 犯 d e f i n i t i o n1 6ag r a p ho nnv e r t i c e s 妇l l e ds u b p a n e y c l i c 矿i tc o n - t a i n sc y c l e so fl e i t h o re v e r yi n t e g e rzw i t h3 z c ( g ) d e f i n i t i o n 1 7a c y c l eci n 口g r a p hgi se x t e n a b l ei ft h e r ei s 口c y c l e i ngs u c ht h a ti y ( ) f = f y ( 回f + 1a n d y ( q 矿( d e f i n i t i o n1 8av e r t e xo fag r a p hg 巧o r d e r 佗i sr - p a n c y c l i c i fi ti s c o n t a i n e d 讥ak - c y c l ef o re v e r yi n t e g e rkb e t w e e nt a n dn a n dg i s v e r t e xr - p a n c y c l i c 矿e v e r yv e r t e xi sr - p a n c y c 托c ， c l e a r l y , a3 - p a n c y c l i ca n dav e r t e x3 - p a n c y e f i cg r a p ha t ep a n c y c l i e a n dv e r t e xp a n c y c l i c ，r e s p e c t i v e l y d e f i n i t i o n1 9ag r a p hgi sy u u yc y c l ee x t e n d a b l e 矿gi sc y c l ee a t e n d - a b l ea n de v e r yv e r t e xo f gl i e so nac y c & o f l e n g t hs 4 1 2 h a m i l t o n i c i t y t h ef i r s ts u f f i c i e n tc o n d i t i o nf o rag r a p ht ob eh a m i l t o n i a ni sd u et o d i r a c 5 1i n1 9 5 2 t h e o r e m1 ( d i r a c 5 】) 巧gi s 口g r a p ho yo r d e r 亿之3s u c ht h a t 6 ( g ) n 2 ，t h e ng i sh a m i l t o n i a n a ni n t e r e s t i n gi m p r o v e m e n to fd i r a c sc o n d i t i o nw a so b t a i n e db y o r e 【1 9 l e m m a1 ( o a e 【1 9 ) l e t “a n dt ，b ed i s t i n c tn o n a d j a c e n tv e r t i c e so f 口g r a p hg 巧o r d e r n2 3s u c ht h a td c ( u ) + d c ( u ) n t h e ngi s h a m i l t o n i a n 矿a n do n l y 矿g + 钍钉妇h a m i l t o n i a n t h e o r e m2 ( o r e 【1 9 ) l e tgb eag r a p ho fo r d e rn 3 i f a 2 ( g ) n ，t h e ng i sh a m i l t o n i a n l e m m a1m o t i v a t e db o n d ya n dc h v 舂t a l 【1 3 t ot h ed e f i n i t i o no ft h e c l o s u r e f o rr e c e n to v e r v i e wo nc l o s u r ec o n c e p t st h er e a d e ri sr e f e r r e d t o 【9 】 b yl e m m a1 e a c ht i m ea ne d g ei sa d d e di nt h ef o r m a t i o no ft h e c l o s u r e ，b o n d ya n dm u r t yg a v e1 1 8t h ef o l l o w i n gt h e o r e m s ： t h e o r e m3 ( b o n d ya n dm u r t y 【1 4 ) as i m p l eg r a p hi sh a m i l t o - n i a nt ia n do n l y 毽i t sc l o s u r ei sh a m i l t o n i a n 5 t h e o r e m 4 ( b o n d ya n dm u r t y 1 4 】) l e tg b ens i m p l eg r a p hw i t h 口3 可a ( g ) i sc o m p l e t e , t h e ng i sh a m i l t o n i a n d i r a c 8c o n d i t i o nw 嬲a l s oe x t e n d e di nt h ef o l l o w i n gd i r e c t i o n t h e o r e m5 ( e r d o s 【2 1 】) l e tgb eag r a p ho f s i z ema n do r d e rn 之3 巧e i t h e r 5 = 6 ( g ) n 2o r m m i n ( n i ? 彬，( k 扎+ 2 2 ) 倒) + 【孚j 2 ) ， t h e ngi sh a m i l t o n i a n t h e o r e m6 ( f a n 【7 ) l e tgb ea2 - c o n n e c t e dg r a p ho nn 3v e r t i c e s a n dl e t a n d “b ed i s t i n c tv e r t i c e so fg 可 d ( 钍，u ) = 2 = m a x d ( v ) ，d ( t ) ) ? 2 2 t h e ngh a snh a m i l t o n i a nc y c l e t h e o r e m7 ( o r e 【2 0 ) l e tgb eag r a p ho o r d e rn 3 f f a 2 ( g ) n + 1 ，t h e ng i sh a m i l t o n i a n c o n n e c t e d t h e o r e m8 ( f a u d r e e ，g o u l da n dj a g o b s o n 【2 4 ) l e tgb eo2 一 c o n n e c t e dg r a p hw i t ho r d e r 扎a n d6 ( g ) t ，矿i ( “) u ) i n t 厂d ra n yn o n a d j a c e n tv e r t i c e sua n du 伽g ，t h e ng i sh a m i l t o n i a n ， p o l i c k 夕【1 0 】d e f i n e du ( u ，勘) 够t h en u m b e ro fc o m p o n e n t so fg i n ( 牡) 】 c o n t a i n i n gn on e i g h b o ro f 口t h e nh ep r o v e dt h ef o l l o w i n gr e s u l t ： 6 t h e o r e m9 ( p o l i c k t 【1 0 】) l e tgb eag r a p hd ，o r d e rn 巧d ( 让) + d ) + m o 茹如( 让，臼) ，u ( t ，) 铊，d re a c hp a i ro ln o n a d j a c e n tv e r t i c e s a n d 仉t h e ng i sh a m i l t o n i a n t h e r ea r em a n yo t h e rs u f f i c i e n tc o n d i t i o n sf o rh a m i l t o n i a n c i t y , i n 【1 6 ， 2 7 1 ，【1 2 ，【2 8 】，【4 】，【6 】， z 5 1 e t c 7 c h a p t e r2 p a n c y c l i c i t y v e r t e xp a n c y c l i c i t y 2 1 p a n c y c l i c i t y i n1 9 7 1b o n d y 【1 1 】p r o p o s e dt h ef o l l o w i n gm e t a c o n j e c t u r e ： a l m o s ta n yn o n t r i v i a lc o n d i t i o no nag r a p hw h i c hi m p l i e st h a tt h e g r a p hi sh a m i l t o n i a na l s oi m p l i e st h a ti t i sp a n c y c l i c ( e x c e p tf o rm a y b e as i m p l ef a m i l yo fe x c e p t i o n a lg r a p h s ) 、 b o n d y 【1 5 p r o v e dt h a t ： t h e o r e m1 0 ( b o n d y 【1 5 ) e v e r yh a m i l t o n i a ng r a p h0 ，o r d e rna n d s i z ee x c e e d i n gn 2 4i sp a n c y c l i c h i se l e g a n tp r o o fi sv e r ys h o r t h i st h e o r e mw a ss t r e n g t h e n e db y h i g g k v i s t ，f a u d r e e ，a n ds c h e l p 【2 3 】，w h os h o w e dt h a t ： ， t h e o r e m1 1 ( h k o g k v i s t ，f a u d r e e ，a n ds g h e l p 【2 3 ) ah a m i l - t o n i a ng r a p hd ，o r d e r 仃a n ds i z ee x c e e d i n g ( n 1 ) 2 4 + 1i sp a n c y c l i c s o r 妇b i p a r t i t e a l t h o u g ht h en u m b e ro fe d g e si n v o l v e dh e r ei so n l ya b o u t 扎2l e s s t h a ni nb o n d y st h e o r e m ，t h ep r o o fi so fs u b s t a n t i a ll e n g t h i n 【1 5 】，b o n d ya l s os h o w e dt h a ta l lg r a p h ss a t i s f y i n go r e sc o n d i t i o n a r ee i t h e rp a n c y c l i co ri s o m o r p i et ok n 2 一f 2 a l d r e s ，h o l t o na n dm i n 【2 2 】r e l a x e do r e sc o n d i t i o nb yc o n s i d e r i n gg r a p h sw i t h0 r 2 n 一1 t h e o r e m1 2 ( a l d r e s ，h o l t o na n dm i n 【2 2 ) 矽gs a t i s f i e s 眈 n 一1 ，t h e ngi sp a n c y e h cu n l e s sg i si s o m o r p h i ct oo n eo it h ef o l l o w i n g g r a p h s ： n ) 8g r a p ho jo r d e rnc o n s i s t i n go ft w oc o m p l e t eg r a p h sj o i n e da tq z t e r t e x , ( b ) as u b g r a p ho jt h ej o i no j ac o m p l e t eg r a p ho r d e rb 一1 ) 2a n da n e m p t yg r a p ho ，o r d e rm + i ) 2 ， ( c ) k 2 以 d ) c 5 t h e o r e m1 3 ( x u 【2 9 】) l e tgb ea2 - c o n n o t e dg r a p hw i t ho r d e rn a n d6 ( g ) 之t ，矿i n ( u ) u ( u ) i n tf o t a n yn o n a d j a c e n tv e r t i c e su a n d t ，讥g ，t h e ng 妇p a n c y c h co rn = 2 t ，g 些托t 9 2 2v e r t e xp a n c y c l i c i t y f o rm a n ys u f f i c i e n tc o n d i t i o n sb o n d y sm e t a c o n j e c t u r eh a sb e e nv e r i - f l e d t h i si sm o t i v a t i o nt oe x a m i n et h e s es u f f i c i e n tc o n d i t i o n se v e nf o r v e r t e xp a n c y c l i c i t y , s i n c ev e r t e xp a n c y c l i e i t yi m p l i e sp a n c y c l i c i t ya n d p a n c y c l i c i t yi m p l i e sh a m i l t o n i c i t y t h e o r e m1 4 ( h e n d r y 【8 】) l e tgb e 口g r a p ho fo r d e rn 3w i t h j ( 回2 + a ) 2 ，t h e ng i sv e r t e xp a n c y c h c t h e o r e m 1 5 ( r a n d e r a t h ，s c h i e r m e y e r ，t e w e se t c1 3 】) l e tg b eag r a p h 盯o r d e r n 3s u c ht h a t6 r 2 f 4 n 3 1 1 t h e ne v e r yv e r t e x o g i sc o n t a i n e d 讯a3 - c y c l e t h e o r e m 1 6 ( h e n d r y 8 】) l e tg b eag r a p ho yo r d e r n 3s u c ht h a t 眈( g ) na n dl e tc b ean o n e x t e n d a b l ec y c 跑o yl e n g t hki ngw i t h 3 k n 一1 t h e ue i t h e r ( dl o eh a v ek 曼n f 2 。t h ev e r t i c e so yci n d u c eac o m p l e t eg r a p h , e v e r y v e r t e x 。o fc i sa d j a c e n tt oa tl e a s to n ev e r t e x v ( c ) 一v ( c ) a n d e a c hv e r t e xy y ( g ) 一y ( 回妇a d j a c e n tt oa tm o s to n ev e r t e xo t h e c y c l ec o r 一砂t h ei n t e g e r sna n dka r ee v e n , t h ev e r t i c e so yci n d u c eab a l a n c e d c o m p l e t eb i p a r t i t eg r a p hw i t ht h ep a r t i t es e t sk ，y ( g ) = v ( c ) u u w i t hl i = i k ia n dt h ev e r t i c e s0 1 u i n d u c eag r a p hh a v i n g 1 0 m i n i m u md e g r e ea tl e a s t ( n k ) 2 i na d d i t i o n , 铲。阢a n dy 巧 ，0 r i ，歹 1 ，2 ，t h e nx y e ( g ) 矿a n do n l y 矿i = 歹 b yu s i n gt h e o r e m1