（基础数学专业论文）全图补图的哈密尔顿性.pdf

y9 0 0 9 8 9 稿要 鲶定图g ，g 匏全圈t ( g ) 是戳v ( c ) u 窘( g ) 强璜焱嶷，对予磐，y y ( r g ) ) ，翅采嚣巍y 在g 中是楣邻魄或耀关的，魁x y 露 ? ( 固) e 令 g 是全图t ( c ) 的补图。在这篇论文巾，我们主要讨论g 的哈密尔 顿链。 瓣一令键莘辫g ，吴宝鬻黎爨与蠹蠢摆在文献( b a s i cp r o p e r t i e so ft o t a l t r a n s f o r m a t i o ng r a p h s ，j m a t h 。s t u d y3 唾( 2 ) ( 2 0 0 1 ) 1 0 9 - 1 1 6 ) 中奔绍了g 的一些基本性质。他们证明了g 一题连邋的当盥仅当g 鼹不是熙图也 不蹩三角形。同时也证明了如采g 是连通的，那么，g 直径不大 予3 。i - i a r a r y 秘n a s h - w i l l i a m s 在文欺( o n e u l e r i a na n dh a m i l t o a i a ng r a p h sa n d l i n eg r a p h s ，c a n a d m a t h + b u l l 8 ( 1 9 6 5 ) 7 0 1 7 0 9 ) 中证明了l ( g ) 怒哈密 尔顿的当盥仅当g 裔条与每条边都关联的闭迹。跳辫的概念采用的是 文( s u b g r a p hd i s t a n c e si ng r a p h sd e f i n e db ye d g et r a n s f e r s d i s c r e t em a t h ， ：7 0 ( ：0 9 7 ) 6 3 - 7 9 ) 审豹定义。鬟葶爨孟在文黻( h a m i l t o n i a n j u m pg r a p h s ，d i s c r e t e m a t h ，2 8 9 ( 2 0 0 4 ) 9 5 _ 1 0 6 ) 中对一个图g 冉勺跳图j ( g ) 是哈密尔顿的绘了一个 简单的充要条件。受上面的龠发，我们证明了k ( g ) 芝6 ( g 一) 一l ， 两鼠，遗一步建嶷了g 怒暗密尔颟的当藏纹当g 不阏稳予 玛。，ir l u 甄+ 甄| s l t l 甄，e | t 2 o 娲，玛+ 盟，恐+ 2 k l ，甄 孛 的任何图。并由此得出g 有完美匹黼的一个充要条件。 荚毽蠲：全避；补圈；跨密尔顿鲻；完美疆配 a b s t r a c t f o rag r a p hg ，t h et o t a lg r a p ht ( g ) o fgi st h eg r a p hw i t hv e r t e xs e t v ( a ) ue ( g ) i nw h i c ht h e v e r t i c e s 。a n dya r ej o i n e db ya ne d g ei fxa n dya r e a d j a c e n to ri n c i d e n ti ng l e tg b e t h ec o m p l e m e n t so ft o t a lg r a p h st ( g ) i nt h i st h e s i s ，w ec o n c e n t r a t eo nt h eh a m i l t o n i c i t yo ft h ec o m p l e m e n t so ft o t a l g r a p h st ( g ) o fs i m p l eg r a p h sg w ub a o y i n d u r e n ga n dm e n gj i x i a n gi n ( b a s i cp r o p e r t i e so ft o t a lt r a n s f o r - m a t i o ng r a p h s ，j m a t h s t u d y3 4 ( 2 ) ( 2 0 0 1 ) 1 0 9 - 1 1 6 ) e s t a b l i s h e ds o m eb a s i c p r o p e r t i e so fg f o rag r a p hg t h e yp r o v e dt h a tg i sc o n n e c t e di fa n d o n l yi fgi sn e i t h e ras t a rn o rat r i a n g l e t h e ya l s op r o v et h a ti fg i sn e i t h e r as t a rn o ra t r i a n g l e ，t h e nd i a m ( g ) 3h a r a r ya n dn a s h w i l l i a m si n ( o n e u l e r i a na n dh a m i l t o n i a ng r a p h sa n dl i n eg r a p h s ，c a n a d m a t h b u l l 8 ( 1 9 6 5 ) 7 0 1 7 0 9 ) p r o v e dt h a tl ( g ) i sh a m i l t o n i a ni fa n do n l yi fgh a sa c l o s e dt r a i li n c i d e n tw i t he a c he d g e w ec a l lt h ec o m p l e m e n to fl i n eg r a p ho fag r a p hg ，t h e j u m pg r a p ho fga d o p t i n gt h en o t i o ni n ( s u b g r a p hd i s t a n c e si ng r a p h sd e f i n e d b ye d g et r a n s f e r s ，d i s c r e t em a t h 1 7 0 ( 1 9 9 7 ) 6 3 - 7 9 ) w ua n dm e n gi n ( h a m i l t o - n i a nj u m pg r a p h s ，d i s c r e t em a t h 2 8 9 ( 2 0 0 4 ) 9 5 - 1 0 6 ) g i v eas i m p l es u f f i c i e n ta n d n e c e s s a r yc o n d i t i o nf o rag r a p hgw h o s ej ( g ) i sh a n f i l t o n i a n m o t i v a t e df r o m t h er e s u l t sa b o v e ，w ep r o v et h a tk ( g ) 6 ( a ) 一la n df u r t h e re s t a b l i s h t h a tg i sh a m i l t o n i a ni fa n do n l yi fgi sn o ti s o m o r p h i ct oa n yg r a p hi n k l ，一r 1 ) u k 1 ，。+ 尬is 1 u t 1 ，t + e lt 2 ) u 玛，k 3 + 1 ，坞+ 2 玛，肠) f i n a l l y , w eg i v eas i m p l es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rag r a p hgw h o s e g h a sap e r f e c tm a t c h i n g k e y w o r d s ：t o t a lg r a p h ；c o m p l e m e n t ；h a m i l t o nc y c l e ；p e r f e c tm a t c h i n g 弛e 弛e s i s 1i n t r o d u c t i o n 1 a l lg r a p h sc o n s i d e r e dh e r ea r ef i n i t e ，u n d i r e c t e da n ds i m p l e w er e f e rt o 1 j f o ru n e x p l a i n e dt e r m i n o l o g ya n dn o t a t i o n sl e tg = ( y ( g ) ，e ( g ) ) b eag r a p h 1 y ( g ) ia n dl e ( g ) | a r ec a l l e dt h eo r d e ra n dt h es i z eo fg ，r e s p e c t i v e l y f o rt w o v e r t i c e sua n duo fg ，i ft h e r ei sa ne d g eej o i n i n gt h e m ，w es a yua n dua x e a d j a c e n t i nt h i sc a s e ，b o t h “a n dva r ee n dv e r t i c e so fe ，a n du ( o r 口) a n d ei ss a i dt ob ei n d e n t t w oe d g e sea n dfa r ea l s oc a l l e dt ob ea d j a c e n ti f t h e yh a v ea ne n dv e r t e xi nc o m m o n f o rx y ( g ) ，l e tg xd e n o t et h e g r a p hb yr e m o v i n gv e r t i c e so fxa n dt h e i ri n c i d e n te d g e sf r o mg ，a n dl e tg e d e n o t et h eg r a p hb yr e m o v i n ga ne d g eef r o mg aw a l ki nci sas e q u e n c e w = v 0 ，e 1 ，”l ，”ko fv e r t i c e sa n de d g e ss u c h t h a t ，f o r1 i ，t h ee d g e e lh a se n d v e r t i c e s q 一1 a n d qi f t h ee d g e se l ：e 2 ，e ko f a w a l k w8 x e d i s t i n c t i sc a l l e dat r a i la n dm o r e o v e r ，i ti sc a l l e dac l o s e dt r a i li fk 0a n dv o = ac l o s e ds p a n n i n gt r a i li sac l o s e dt r a i lc o n t a i n i n ga l lt h ev e r t i c e so fg f o rav e r t e x o fg ，i ft h e r ei sn oc o n f u s i o n ，t h ed e g r e ed a 0 ) i ss i m p l y d e n o t e db yd ( ) 尼( u ) d e n o t e st h es e to fa l le d g e si n c i d e n tw i t h ，t h en e i g h - b o r h o o d b ( ) o f i st h es e to fa l lv e r t i c e so fga d j a c e n tt o t h es y m b o l s ( g ) ，巧( g ) ，u ( g ) ，k ( g ) ， ( g ) a n da ( g ) d e n o t et h em a x i m n n ld e g r e e ，t h em i n i m u md e g r e e ，t h en u m b e ro fc o m p o n e n t s ，t h ec o n n e c t i v i t y , t h ee d g ec o n n e c t i v i t y , a n dt h ei n d e p e n d e n c en u m b e ro fg r e s p e c t i v e l y a su s u a l ，r ，ga n d ga x er e s p e c t i v e l y , t h ep a t h ，c y c l e ，a n dc o m p l e t e g r a p ho fo r d e rn f o rt w op o s i t i v ei n t e g e rra n d8 ，珥5i st h ec o m p l e t eb i p a r t i t e g r a p hw i t ht w op a r t i t es e t sc o n t a i n i n gra n d8v e r t i c e s i np a r t i c u l a r ，k 1 ，5i s c a l l e das t a rf o rs 2 ，k 15 + ei so b t a i n e df r o mk 1sb ya d d i n gan e w e d g ew h i c hj o i n st w ov e r t i c e so ft h es e tc o n t a i n i n gsv e r t i c e s ，w h i l ef o rs 3 ， t h et h e s i s2 ( ，5 + 2 e hi so b t a i n e df r o mk 1 ，sb ya d d i n gt w o n e we d g e sw h i c hj o i nv e r t i c e s o ft h es e tc o n t a i n i n gsv e r t i c e sa n dh a v eav e r t e xi nc o m m o n ，o t h e r w i s e ，w e d e n o t ei tb y ( k 1 。+ 2 e ) 2 弼。d e n o t e st h eg r a p hb ya d d i n gan e wv e r t e xa n d j o i n i n gi tt oe x a c t l yo n ev e r t e xo fd e g r e eo n eo fk i pj d e n o t e st h eg r a p h r e s u l t i n gf r o m b yd e l e t i n ga ne d g e w es a yt w og r a p h sga n d ha i ed i s j o i n t i ft h e yh a v en 0v e r t e xi nc o m m o n ，a n dd e n o t et h e i ru n i o nb yg + 日：i ti sc a l l e d t h ed i s j o i n tu n i o no fga n dh t h ed i s j o i n tu n i o no fkc o p i e so fgi sw r i t t e na s k g t h e j o i n g v ho f ga n d h i s t h eg r a p ho b t a i n e d f r o m g + hb y j o i n i n g e a c hv e r t e xo fgt oe a c hv e r t e xo fh t h el i n eg r a p hl ( g ) o fgi st h eg r a p hw h o s ev e r t e xs e ti se ( g ) i nw h i c h t w ov e r t i c e sa r ea d j a c e n ti fa n do n l yi ft h e y8 i ea d j a c e n ti ngt h et o t a lg r a p h t ( g ) o fg i st h eg r a p hw h o s ev e r t e xs e ti sv ( a ) ue ( g ) i nw h i c ht w ov e r t i c e s a r ea d j a c e n ti fa n do n l yi ft h e ya r ea d j a c e n to ri n c i d e n ti ng t h ec o m p l e m e n to fgi st h eg r a p hw i t ht h es a x n ev e r t e xs e ta sg ，b u tw h e r e t w ov e r t i c e sa r ea d j a c e n ti fa n do n l yi ft h e ya r en o ta d j a c e n ti ng w ec a l lt h e c o m p l e m e n to fl i n eg r a p hl ( g ) t h ej u m pg r a p hj ( c ) o fg ，f o l l o w e dt h en o t i o n i n 【2 】w ed e n o t et h ec o m p l e m e n to ft o t a lg r a p ht ( c ) o fgb yg i t sv e r t e x s e ti sv ( g ) ue ( c ) i nw h i c ht h ev e r t i c e sza n dyo ej o i n e db ya ne d g ei fo n e o ft h ef o l l o w i n gc o n d i t i o n sh o l d s ：( i ) z ，y v ( v ) a n dt h e ya r en o ta d j a c e n ti n g ，( i i ) x ，y e ( g ) a n dt h e ya t en o ta d j a c e n ti ng ，( i i i ) o n eo fzm a dyi si n v ( a ) a n dt h eo t h e ri si ne ( g ) ，a n dt h e ya r en o ti n c i d e n ti ng o n ec a n s e e t h a tg c o n t a i n st h ej u m pg r a p hj ( a ) a sa ni n d u c e ds u b g r a p h w ua n dm e n g 【3 】g e n e r a l i z e dt h ec o n c e p to ft o t a lg r a p h st ot o t a lt r a n s f o r m a t i o ng r a p hg 。”w i t h 嚣，y ，z 一，+ ) ，w h e r eg + + + i se x a c t l yt h et o t a l g r a p ho fg ，a n dg i st h ec o m p l e m e n to fg + + + f l e i s c h n e ra n dh o b b s 4 t h e 皿e s i s3 s h o w e dt h a tg + + + i sh a m i l t o n i a ni fa n do n l yi fgc o n t a i n sa j le p s s u b g r a p h w er e f e rr e a d e r st o 【5 】f o rt h em o r er e s u l t sa n dp r o b l e m so ng 。h a r a r y a n dn a s h - w i l l i a m sf 6 】p r o v e dt h a tl ( g ) i sh a m i l t o n i a ni fa n do n l yi fgh a s ac l o s e dt r a i li n c i d e n tw i t he a c he d g e w ec a l lt h ec o m p l e m e n to fl i n eg r a p h o fag r a p hg ，t h ej u m pg r a p ho fga d o p t i n gt h en o t i o ni n 【2 】w ua n dm e n g 7 g i v eas i m p l es u f f i c i e n ta n dn e c e s s a r yc o n d i t i o nf o rag r a p hc w h o s ej ( c ) i sh a m i l t o n i a nm o t i v a t e df r o mt h er e s u l t sa b o v e ，i nt h i sn o t ew ep r o v et h a t k ( g ) 6 ( c ) 一1a n df u r t h e re s t a b l i s ht h ef o l l o w i n g t h e o r e m1 1 l e tgb eag r a p h t h e ng 拈h a m i l t o n i a ni a n do n 坷 矿g 拈n o ti s o m o r p h i cf oa n yg r a p hi n k i ，ir 1 ) u k 1 p + ( 1 8 1 ) u 蜀，t + e it 2 ) u 凰，玛+ ，( 3 + 2 k 1 ，甄) n e 码e s i s 2s o m eb a s i c s 4 w es t a r tw i t hs o m es i m p l eo b s e r v a t i o n s l e tgb eag r a p ho fo r d e rpa n d s i z eq t h e nt h eo r d e ro fg i sp + q f o rs i m p l i c i t y , l e tu sd e n o t et h ed e g r e e o f av e r t e xzo f g b yd c 0 ) c l e a r l y , i fe = 札 e ( a ) a n d 叫y ( g ) ， t h e nd c 一( e ) = p + q d ( u ) 一d ( v ) 一1 ，d a ( ) = j ，+ q 一2 d ( w ) 一1t h e o r d e ro fj ( a ) i sqa n dd j ( c ) ( e ) = q 一4 ( 4 ) 一d ( v ) + 1f o re = “ e ( g ) i t i sa l s oo b v i o u st h a t6 ( g ) = p + q 一2 a ( g ) 一1 w es h o wa l lt h eg r a p h so f o r d e r4a n dt h e i rc o r r e s p o n d i n gt r a n s f o r m a t i o ng r a p h sg i nf i g u r e1 1 2 ff 4 3 l 4 2 j3 ：因： 谕： 固 炱 盛 4 l 31 l - i 2 卜“ 1 凶： 1 冈4 1 因： 1 _ - 2 3 _ 4 2 、32 斗3 2 网3凼 ，涡iq ? 八 公 n 器4毕 吲 l e m m a2 1 f o rag r a p hg ，1 1 eh a v eo ( g ) = 3 矿a ( c ) = l ，a n d a ( g ) = a ( g ) + 1 ，o t h e r w i s e p r o o f i f ( g ) = 0 ，t h e ng i sac o m p l e t eg r a p h ：s oo ( g ) = 1 i fz x ( a ) = 1 ，t h e ngc o n s i s t so fs o m ei s o l a t e d v e r t i c e sa n di s o l a t e de d g e s l e te z ( a ) w i t h 让a n du8 u si t st w oe n dv e r t i c e si ngo b v i o u s l y , ， ，e ) i s a ni n d e p e n d e n ts e to fg o nt h eo t h e rh a n d ，l e tsb ea ni n d e p e n d e n ts e t n et h e s i s 5 o fg t h e ns i n c ez x ( a ) = 1 ，w eh a v el s ne ( g ) l5la n dl s n 矿( g ) j 2 ， a n ds ol s i 曼3 h e n c e ，i fa ( c ) = 1 ，d ( g 一) = 3 n e x tw ea s s u m et h a ta ( a ) 22 f i r s tn o t et h a tf o rav e r t e x y ( g ) ， u 七( ) i sa ni n d e p e n d e n ts e to fc ，a n ds i n c ef 七( 口) j = d ( “) ，w eh a v e ( g 一) ( g ) + 1 n o w l e t s b e a n i n d e p e n d e n t s e to f g i f l s h y ( g ) i = 2 ，t h e ni s ne ( g ) | sl ，a n ds oi sj 兰3 a ( c ) + l ，i fi sny ( g ) i 2 ，t h e n l s nf ( g ) i = 0 ，a n ds i sa c l i q u eo fg ，s oi s l a ( c ) + l ；i fi s ny ( g ) i = 1 ， a n ds a yu v ( a ) n s ，t h e ns n e ( c ) 七( 口) ，s ol s isa ( c ) + 1 i na n yc a s e ， w eo b t a i ni s 茎a ( a ) + 1t h er e s u l tt h e nf o l l o w s 口 w ua n dm e n gf 3 】p r o v e dt h a ti fa g r a p hgi s o m o r p h i ct on e i t h e r as t a rn o r a t r i a n g l e t h e ng i sc o n n e c t e d t h e o r e m2 2 f o ra n yg r a p hg ，k ( g 一) 芝d ( g ) 一1 ，a n de q u a l i t y h o l d si fa n do n l y 矿a ( c ) = 2a n dgc o n t a i n sat r i a n g l e p r o o f a s s u m et h a tsi sam i n i m u mc u to fg 一一一i t hj s l 。 t h u sg i sh a m i l t o n i a nb yc o r o l l a r y2 4 f i n a l l yw ec o n s i d e rt h ec a s ew h e ng 兰虬vk aw i t hs 2 ，t2 2s i n c e t h et h e s i s p = s + t ，q = s t + 丛等卫，a n d ( g ) = s + t 一1 ，w eh a v e p + 口一3 ( g ) 一2 = i 8 2 5 2 一9 一 i 5 s + t ( s t ( s 一2 ) + 1i +一) + 5 z s + 2 ( p 2 ) + 1 1 ) 一3 t h e r e f o r e ，i fs 3t h e na ( c ) 2 ，a n dg i sh a m i l t o n a nb yc o r o l l a r y2 4 f o r8 = 2 ，l e tv ( c ) = u ，u 7 ) u u l ，v 2 ，饥) ，e ( a ) = e ) u e l ，e 2 ，e t ) u e i ，e ：，e ：) ，w h e r ee = ie i 一饥a n de ：= u t v if o re a c h i = l ，2 ，t t h e n w ec a n f i n da h a m i l t o nc y c l e co f g i f t i so d d ，c i s e l e ；e e ：+ l - e ：一1 仳e ：e t 札7 e 2 e ：岛+ 1 e ：一2 e 一l e c v 2 v 3 - v t e l ；i f t i se v e na n d t 24 ，c i se , 4 b e ，+ 1 e t l u e 2 e t u e i e i + 1 e ：- 龟e ；一1 l e v 2 v 3 u t e l i f t = 2 ，t h e n g = 酊i t i se a s y t oc h e c k t h a t ( 巧) i s h a m i l t o n i a n 几 n e x tw ei n t r o d u c ead e f i n i t i o n l e tgb eag r a p ho fo r d e rpa n ds i z e q ， e = 让 e ( g ) w ec a l le i sr e m o v a b l ei fd ( u ) + d ( ) i w e w i l lu s et h ef o l l o w i n gr e s u l t l e m m a 3 2 ( b o n d ya n dc h v a t a i 9 0l e tg b eag r a p hw i t ho r d e r pa n ds i z e qa n dl e tua n dub en o n a d j a c e n tv e r t i c e si ngs u c ht h a td ( u ) + d ( v ) p + q t h e ngi sh a m i l t o n i a nt 厂a n do n l yi fg + u vi sh a m i l t o n i a n c o r o l l a r y3 3 l e tgb eng r a p hn n de e ( g ) r e m o v a b l e 盯( g e ) i sh a m i l t o n i a n ，t h e ng i sh a m i l t o n i a n t b et 血e s i s1 1 p r o o f l e tua n dub e t h e t w oe n dv e r t i c e so fe i n g n o t e t h a tu a n dua r en o t a d j a c e n ti ng 一，b u tt h e ya r ea d j a c e n ti n ( g e ) s i n c ee i sr e m o v a b l e ， p - i - q 一1 d ( u ) + d ( ) 吐碧，ei sa d j a c e n tt ot w oc o n s e c u t i v ev e r t i c e so fc t h u sg + “口i s h a m i l t o n i a n 口 i ti ss t r a i g h t f o r w a r dt oc h e c kt h a t3 k ii st h eu n i q u eg r a p hgo fo r d e rn o m o r et h a n3s u c ht h a tg i sh a m i l t o n i a n ，a n dk 4 ，2 魁，p 4 ，c 4 ，尬一ea r ea l l t h eg r a p h sgo fo r d e r4s u c ht h a tg i sh a m i l t o n i a nf r o mf i g u r e1t h e r e a r e3 4g r a p h so fo r d e r5 ( s e e 【1 0 ) ，w h i c ha r et r e a t e di nt h en e x tl e m m a l e m m a3 4 l e tgb eag r a p ho so r d e r5 l sgi sn o ti s o m o r p h i ct o l ，4 ，j f l ，4 + e ，k 1 ，3 + k 1 ，k a + 2 k 1 ，t h e ng i s h a m i l t o n i a n p r o o f l e tpa n dqb et h eo r d e ra n dt h es i z eo fg ，r e s p e c t i v e l y i fa ( c ) = 0 ， t h e ng i st h ec o m p l e t eg r a p ho fo r d e r5 ，a n di sh a m i l t o n i a ni f ( g ) = l ， t h e np + q 6 ，g i sh a m i l t o n i a nb yc o r o l l a r y2 4a sf o ra ( a ) = 2 ，c l e a r l y p + q 7 i fp + q = 7 ，t h e ng 竺p 3 + 2 k 1o n ec a ne a s i t yc h e c kt h a t ( b + 2 k i ) i sh a m i l t o n i a n i f p + q 8 ，a n ds i n c eg 笋k a + 2 k 1 ，t h e nb y c ( ) io l l a r y2 4g i sh a m i l t o n i a n n et h e s i s 1 2 n o wa s s u m ea ( c ) = 3 i fg 6 ，t h e np + q 1 1 ，s og i sh a m i l t o n i a n b yc o r o l l a r y24 n e x tw ec o n s i d e rt h ee a s e3 gs5 】fgi sn o tc o n n e c t e d ， a n ds i n c ea ( a ) = 3 ，i tf o l l o w st h a tg 型g 1 + k ls u c ht h a tg 1i sac o n n e c t e d g r a p ho f o r d e r4s i n c e g 笋k 1 ，3 十k 1 ，g i l ，3 + e ，k 4 一e ：) o n ec a y ie a s i l y c h e c k t h a t g i sh a m i l t o n i a n i f g i sc o n n e c t e d ，t h e nq 5 1 = 4i f q = 4 ， t h e ng 型蟛a n dt h u s ( 巧，3 ) i sh a m i l t o n i a n i fq = 5 ，s i n c ea ( c ) = 3 ， t h e r ee x i s t sav e r t e xu v ( a ) w i t hd c ( “) = 1 l e tvb et h en d 曲b o ro f i n 口+ o 一】 gs od a ( u ) + d g 扣) = 1 + d c ( v ) 4 二# ，o ru ui sr e m o v a b l e i ti s o b v i o u st h a tg 一“ui sn o tc o n n e c t e d ，a n dt h u s ( g m 7 ) i sh a m i l t o n i a n h e n c eg i sh a m i l t o n i a n f i n a l l yl e ta ( c ) = 4 t h e n ，s i n c eg 学硒，4 ，4 + e ，gi sc o n n e c t e da n d q 6 i fq 9 ，t h e ng i s m m i l t o n i a nb yc o r o l l a r y2 4n e x tw ec o n s i d e r 6 q 8l e tw v ( a ) w i t hd ( w ) = 4 ，a n dg = g 一 t h e ng i sa g r a p ho fo r d e r4a n ds i z eb e t w e e n2a n d4 i tf o u o w st h a tf o r6sq 曼8 ，g m u s tb eo n eo fg r a p h sd e p i c t e di nf i g u r e2b e l o wo n ec a nc h e c kt h a tg i s h a m i l t o n i a f o re a c hg 口 x 厶凶卧肜令 abc f i g u r e2 g n et 血e s i s 4t h ep r o o fo ft h e o r e m1 1 f i r s t ，w ep r o v et h en e c e s s i t yi fgi si s o m o r p h i ct oo n eo f 凰 r ，硒，s + k 1 ， a n dk 1e + ef o rs o m er 1 ，s 1 ，a n dt 2 ，i ti st r i v i a lt oc h e c kt h a tg i sr i o th a m i l t o n i a n a l s o ，f o re v e r yg r a p hgi n 蚝，娲+ k 1 ，蚝+ 2 k 1 ，凰) ， c i sn o th a m i l t o n i a n n e x t ：w ep r o v et h es u f f i c i e n c yo ft h et h e o r e m1 1b yc o n t r a d i c t i o ns u p p o s e t h a tt h e r ee x i s t sag r a p hgn o ti s o m o r p h i ct oa n yg r a p hi nt h eh y p o t h e s i so f t h e o r e m11 ，s u c ht h a tg i sn o th a m i l t o n i a n f u r t h e r m o r e ，w ea s s u m et h a t g i ss u c ha g r a p ho f m i n i m u m p + q b y t h er e s u l t s i n s e c t i o n3 ，w e h a v e p 6 h e n c e ，i f a ( a ) 2 ，t h e np + q 6 + a ( c ) 3 a ( g ) + 2 s i n c eg 蚝十2 k l ， b yc o r o