（应用数学专业论文）tutte子图方法及其应用.pdf

摘要 摘要 哈密顿圈问题是数学和计算机科学中最重要的问题之一，它也与著名的 四色定理有着密切联系。1 9 3 1 年，w h i t n e y 在a n n a l so fm a t h e m a t i c s ) ) 中发 表文章证明了每一个4 连通平面三角剖分图都含有哈密顿圈( 因此，也是4 面 可着色的) 。1 9 5 6 年，t u t t e 把w h i t n e y 的结果推广到所有4 连通平面图，而 后t h o m a s s e n 在1 9 8 3 年对此作了进一步拓展。这些证明是借助于某些特殊的路 和圈的存在性加以归纳而得到的( 后来称这些特殊的路和圈为t u t t e 子图) 。 t u t t e 子图方法如今已经被广泛应用到证明可嵌入各种曲面的图中长路和 长圈的存在性。例如：t h o m a s e n 在1 9 8 3 年证明了p l u m m e r 提出的猜想一每一 个4 连通平面图都是哈密顿连通的，t h o m a s 和郁星星解决了多面体领域的权 威g r i i n b a u m 在1 9 7 0 年提出的把t u t t e 的结果推广到射影平面的猜想一所有4 连 通射影平面图都含有哈密顿圈，郁星星在1 9 9 7 年证明了t h o m a s s e n 提出的猜 想一所有( 定向和非定向) 曲面上的5 连通“局部平面三角剖分图都含有哈 密顿圈，等等。 在本文中，通过运用t u t t e 子图方法，我们主要得到两个结果。第一个是关 于m a l k e v i t c h 在1 9 8 8 年提出的一个猜想( 第二章) ，第二个是关于3 连通3 正则 不含三角形的平面图中的最大二部子图问题( 第三章) 。 在第一章中，我们主要介绍在本文中用到的一些基本定义和记号，并给出 关于t u t t e 子图方法的一个简要概述。 在第二章中，我们考虑m a l k e v i t c h 提出的猜想一如果一个仇个项点的4 连通 平面图含有长度为4 的圈，那么它一定含有长度为k 的圈，其中k n ，n 一 1 ，3 。已有的结果证明了每一个n 个顶点的4 连通平面图都含有长度为尼的 圈，其中k 佗，竹一1 ，几一6 ) 且k 3 。通过运用t u t t e 子图和可收缩子图 的方法，我们证明每一个n 个顶点( 礼9 ) 的4 连通平面图总是含有不包含某 一给定项点的长度为n 一6 的圈。运用这一结果( 以及f o n t e t 和m a r t i n o v 的一个 定理) ，我们进一步证明每一个n 个顶点( 佗1 0 ) 的4 连通平面图都含有长度 为n 一7 的圈。 在第三章中，我们研究3 连通3 正则不含三角形的平面图中的最大二部子图 问题。最近，t h o m a s s e n 证明了每一个3 连通3 正则不含三角形的平面图g 中都 摘要 含有一个至少有婴掣一丢条边的二部子图，改进了已知的( 3 正则不含三角 形的图的) 下界掣。很容易可以看出，如果s 是平面图g 的一个边子集合 使得g s 是一个二部图，则在g 的对偶图中删除s 所对应的边后得到的图是 一个偶图。通过运用这一性质以及t u t t e 子图方法，t h o m a s s e n 证明了如下等 价结果：每一个最小度至少为4 的平面三角剖分图g 都含有一个至多有掣条 边的边子集合使得在g 中删除这些边后得到的图是一个偶图。我们通过拓 展t h o m a s s e n 在t u t t e 圈上的, 、 9 i v ( g ) i 一百9 ，这表明每一个3 连 通3 正则不含三角形的平面图g 中都含有一个至少有型等型一杀条边的二部子 图。 关键词：t u t t e 子图，可收缩子图，平面图，二部子图，三角剖分图 a b s t r a c t a b s t r a c t l h eh a m i l t o nc y c l ep r o b l e mi so n eo ft h em o s ti m p o r t a n tp r o b l e m si nm a t h - e m a t i c sa n dc o m p u t e rs c i e n c e i ti sa l s or e l a t e dt ot h ef a m o u sf o u rc o l o rt h e o - r e m i n1 9 3 1 ，w h i t n e yp r o v e dt h a te v e r y4 - c o n n e c t e dp l a n a rt r i a n g u l a t i o nh a sa h a m i l t o nc y c l e ( a n dh e n c e ，i s4 - f a c e - c o l o r a b l e ) i n1 9 5 6 ，t u t t eg e n e r a l i z e dw h i t n e y sr e s u l tb ys h o w i n gt h a te v e r y4 - c o n n e c t e dp l a n a rg r a p hc o n t a i n sah a m i l t o n c y c l e t h i sw a sf u r t h e re x t e n d e db yt h o m a s s e ni n1 9 8 3 t h e s ep r o o f sw e r eb y i n d u c t i o na n dr e l i e do nt h ee x i s t e n c eo fc e r t a i np a t h sa n dc y c l e s ( 1 a t e rc a l l e d t u t t es u b g r a p h s ) t h et u t t es u b g r a p ht e c h n i q u eh a sn o wb e e nu s e de x t e n s i v e l yt op r o v et h e e x i s t e n c eo fl o n gp a t h sa n dc y c l e si ng r a p h se m b e d d a b l eo ns u r f a c e s t h o m a s s e n p r o v e dt h a te v e r y4 - c o n n e c t e dp l a n a rg r a p hi sh a m i l t o n i a n c o n n e c t e d ( c o n j e c - t u r e db yp l u m m e t ) ，t h o m a sa n dy us h o w e dt h a t4 - c o n n e c t e dp r o j e c t i v e - p l a n a r g r a p h sa r eh a m i l t o n i a n ( c o n j e c t u r e db yg r f i n b a n m ) ，y up r o v e dt h a t5 - c o n n e c t e d “l o c a l l yp l a n a r ”t r i a n g u l a t i o n so fa n ys u r f a c ea r eh a m i l t o n i a n ( c o n j e c t u r e db y t h o m a s s e n ) ，e t c i nt h i st h e s i s ，w ep r e s e n tt w or e s u l t sb ya p p l y i n gt h et u t t es u b g ：r a p ht e c h n i q u e t h ef i r s to n ed e a l sw i t ha no l dc o n j e c t u r eo fm a l k e v i t c h ( c h a p t e r2 ) ，w h i l e t h es e c o n do n ec o n c e r n st h em a x i m u mb i p a r t i t es u b g r a p h si n3 - c o n n e c t e dc u b i c t r i a n g l e - f r e ep l a n a rg r a p h s ( c h a p t e r3 ) i nc h a p t e r1 ，w ei n t r o d u c es o m eb a s i c t i o nw h i c ha r eu s e dt h r o u g h o u tt h et h e s i s 1 i t e r a t u r ed e a l i n gw i t ht u t t es u b g r a p h s g r a p ht h e o r e t i cd e f i n i t i o n sa n dn o t a - w ea l s op r o v i d eab r i e fs u r v e yo ft h e i nc h a p t e r2 ，w ec o n s i d e rac o n j e c t u r eo fm a l k e v i t c ht h a te v e r yn - v e r t e x4 - c o n n e c t e dp l a n a rg r a p hc o n t a i n sac y c l eo fl e n g t hkf o re v e r yk 礼，佗一1 ，3 】- i fi ta d m i t sac y c l eo fl e n g t h4 p r e v i o u sr e s u l t ss h o w e dt h a te v e r yn v e r t e x4 - c o n n e c t e dp l a n a rg r a p hh a sac y c l eo fl e n g t hkf o re v e r yk 佗，礼一1 ，礼一6 ) w i t h 忽3 b yc o m b i n i n gt u t t es u b g r a p h sa n dc o n t r a c t i b l es u b g r a p h s ，w ep r o v e t h a tf o ra n y 礼一v e r t e x4 - c o n n e c t e dp l a n a rg r a p hg ( w i t hn 9 ) a n da n yv e r t e x vo fg ，t h e r ea l w a y se x i s t sac y c l eco fl e n g t hn 一6i ngs u c ht h a tv 譬y ( c ) i i i a b s t r a c t w et h e nu s et h i sr e s u l t ( a sw e l la sar e s u l to ff o n t e ta n dm a r t i n o v ) t os h o wt h a t e v e r y4 - c o n n e c t e dp l a n a rg r a p h w i t hnv e r t i c e sc o n t a i n sac y c l eo fl e n g t hn 一7 p r o v i d e d 亿1 0 i nc h a p t e r3 ，w es t u d yt h em a x i m u mb i p a r t i t es u b g r a p h si n3 - c o n n e c t e d c u b i ct r i a n g l e - f r e ep l a n a rg r a p h s t h o m a s s e nr e c e n t l yp r o v e dt h a ti fg i sa3 一 c o n n e c t e dc u b i ct r i a n g l e f r e ep l a n a rg r a p ht h e ngc o n t a i n sab i p a r t i t es u b g r a p h w i t ha tl e a s t 划2 4 6 7e d g e s ，i m p r o v i n gp r e v i o u s l yk n o w nl o w e rb o u n d6 1 v 5 ( g ) l ( f o rc u b i ct r i a n g l e - f r e eg r a p h s ) i ti se a s yt os e et h a ti fg i sap l a n eg r a p ha n d s e ( g ) s u c ht h a tg s i sb i p a r t i t e ，t h e nw eo b t a i na ne v e ng r a p hf r o mt h e d u a lg r a p ho fgb yd e l e t i n gi t se d g e sc o r r e s p o n d i n gt oe d g e si ns w i t ht h i s o b s e r v a t i o na n db yu s i n gt h et u t t es u b g r a p ht e c h n i q u e ，t h o m a s s e np r o v e dt h e f o l l o w i n ge q u i v a l e n tr e s u l t ：i fg i sap l a n a rt r i a n g u l a t i o nw i t hm i n i m u md e g r e e a tl e a s t4 ，t h e ngh a sas e to fa tm o s t 7 i v l ( ：广g 一) ie d g e sw h o s ed e l e t i o nr e s u l t si n a ne v e ng r a p h w ee x t e n dt h o m a s s e n st e c h n i q u eb yp r o v i n gs t r o n g e rr e s u l t so n t u t t e c y c l e sa n di m p r o v et h i su p p e rb o u n dt o 哗掣一杀t h i si m p l i e st h a te v e r y 3 - c o n n e c t e dc u b i ct r i a n g l e - f r e ep l a n a rg r a p hgc o n t a i n sab i p a r t i t es u b g r a p hw i t h a tl e a s t 3 9 1 v r 9 ( g ) i 一9 1 6e d g e s k e y w o r d s ：t u t t es u b g r a p h ，c o n t r a c t i b l es u b g r a p h ，p l a n a rg r a p h ，b i p a r t i t es u b - g r a p h ，t r i a n g u l a t i o n a m ss u b j e c tc l a s s i f i c a t i o n ( 2 0 0 0 ) ：0 5 c 3 8 ，0 5 c 4 5 ，0 5 c 3 5 i v 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：在疚 知。矿年石月牛日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年 月日 各密级的最长保密年限及书写格式规定如下： ! 一 ；内部5 年( 最长5 年，可少于5 年) | 秘密l o 年( 最长1 0 年，可少于l o 年)| ； i 机密2 0 年( 最长2 0 年，可少于2 0 年)i | ，。一。、。j 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均己在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名：徨疚 2 0 0 9 年石月铲e l c h a p t e r1 i n t r o d u c t i o n i nt h i sc h a p t e r ，w ep r e s e n tb a s i cn o t i o n so fg r a p ht h e o r ya n di n t r o d u c et h e b a c k g r o u n do ft h et u t t es u b g r a p ht e c h n i q u e 1 1b a s i cd e f i n i t i o n sa n dn o t a t i o n t h i ss e c t i o np r o v i d e ss o m eb a s i cg r a p ht h e o r e t i cd e f i n i t i o n s ( s e e 【4 】) a n d n o t a t i o nn e c e s s a r yt os t a t eo u rm a i nr e s u l t s o t h e rd e f i n i t i o n sw i l lb em a d ea s n e c e s s a r y a g r a p hg i sa no r d e r e dp a i r ( y ( g ) ，e ( g ) ) c o n s i s t i n go fas e tv ( g ) o fv e r t i c e s a n das e te ( g ) ，d i s j o i n tf r o my ( g ) ，o fe d g e s ，t o g e t h e rw i t ha l li n c i d e n c ef u n c t i o n 矽gt h a ta s s o c i a t e sw i t he a c he d g eo fg a nu n o r d e r e dp a i ro f ( n o tn e c e s s a r i l y d i s t i n c t ) v e r t i c e so fg t h en u m b e r so fv e r t i c e sa n de d g e si nga r ec a l l e dt h e o r d e ra n ds i z eo fg r e s p e c t i v e l y i fei sa ne d g ea n dua n dva r ev e r t i c e ss u c ht h a t 妒g ( e ) = u ，u ) ，t h e n ei ss a i d t oj o i nua n dv ，a n dt h ev e r t i c e sua n dva r ec a l l e d t h ee n d so fe f o rn o t a t i o n a ls i m p l i c i t y , w ew r i t el t vf o rt h eu n o r d e r e dp a i ru ，口) t h ee n d so fa ne d g ea r es a i dt ob ei n c i d e n tw i t ht h ee d g e ，a n dv i c ev e r s a t w o v e r t i c e sw h i c ha r ei n c i d e n tw i t hac o m m o ne d g ea r ea d j a c e n t ，a sa r et w oe d g e s w h i c ha r ei n c i d e n tw i t hac o m m o nv e r t e x a n dt w od i s t i n c ta d ja c e n tv e r t i c e sa r e n e i g h b o r s t h es e to fn e i g h b o r so fa v e r t e xui ngi sd e n o t e db yn o ( v ) i fa n y t w ov e r t i c e so fga r ea d ja c e n t t h e ng i sc o m p l e t e ac o m p l e t eg r a p ho fo r d e rn i sd e n o t e db y c h a p t e r1 i n t r o d u c t i o n a g r a p hi sf i n i t ei fb o t hi t sv e r t e xs e ta n de d g es e ta r ef i n i t e ；o t h e r w i s e ，i ti s i n f i n i t e a ne d g ew i t hi d e n t i c a le n d si sc a l l e dal o o p ，a n da ne d g ew i t hd i s t i n c t e n d sal i n k t w oo rm o r el i n k sw i t ht h es a m ep a i ro fe n d sa x es a i dt ob ep a r a l l e l e d g e s ag r a p hi ss i m p l ei f i th a sn ol o o p so rp a r a l l e le d g e s t h r o u g h o u tt h e t h e s i s ，w eo n l yc o n s i d e rf i n i t es i m p l eg r a p h s t h ed e g r e eo fav e r t e xvi nag r a p hg ，d e n o t e db yd g ( v ) ，i st h en u m b e ro f e d g e so fgi n c i d e n tw i t hv ag r a p hg i sk r e g u l a ri fd a ( v 1 = kf o re v e r yv e r t e x v y ( g ) w es a yt h a tag r a p hi sc u b i ci fi t i s3 - r e g u l a r ag r a p hg i ss a i dt o b es u b c u b i ci fgh a sm a x i m u md e g r e ea tm o s tt h r e e w ew r i t ea ：= bt od e f i n eaa sb o rt or e n a m eba sa l e tgb eag r a p h w es a yt h a tag r a p hh i sas u b g r a p ho fgi fv ( h ) 垦v ( a ) a n de ( h ) e ( g ) ；m o r e o v e r ，hi sas p a n n i n gs u b g r a p ho fgi fhi sas u b g r a p h o fga n dv ( h ) = y ( g ) as u b g r a p hho fgi sc a l l e di n d u c e di ff o ra n yt w o v e r t i c e su ，v v ( h ) s u c ht h a tu v e ( g ) ，w ea l w a y sh a v eu v e ( 日) f o ra n y s y ( g ) ，w eu s ea s 】t od e n o t et h es u b g r a p ho fg i n d u c e db ys f o ra n y s u b g r a p hho fg ，w ew r i t ea h ：= g y ( 日) 】 aw a l ki nag r a p hgi sas e q u e n c ev o e l v l v l l e l v l w h o s et e r m sa x ea l t e r - n a t e l yv e r t i c e sa n de d g e so fg ( n o tn e c e s s a r i l yd i s t i n c t ) ，s u c ht h a tv i 一1a n dv i a r et h ee n d so fe if o rl i 1 ap a t hi sas i m p l eg r a p hw h o s ev e r t i c e sc a n b ea r r a n g e di nal i n e a rs e q u e n c ei ns u c haw a yt h a tt w ov e r t i c e sa r ea d ja c e n ti f t h e ya r ec o n s e c u t i v ei nt h es e q u e n c e ，a n da r en o n a d j a c e n to t h e r w i s e l i k e w i s e ，a c y c l eo nt h r e eo rm o r ev e r t i c e si sas i m p l eg r a p hw h o s ev e r t i c e sc a nb ea r r a n g e d i nac y c l i cs e q u e n c ei ns u c haw a yt h a tt w ov e r t i c e sa r ea d ja c e n ti ft h e ya r ec o n - s e c u t i v ei nt h es e q u e n c e ，a n da r en o n a d ja c e n to t h e r w i s e ac h o r do fac y c l ec i sa ne d g ew i t hb o t he n d sl y i n go ncb u ti t s e l fi sn o ta ne d g eo fc t h el e n g t h o fap a t ho rac y c l ei st h en u m b e ro fi t se d g e s t h el e n g t ho fal o n g e s tc y c l e i nag r a p hi si t sc i r c u m f e r e n c e ac y c l eo fl e n g t ht h r e ei sat r i a n g l e ag r a p h i ss a i dt ob et r i a n g l e - f r e ei fi tc o n t a i n sn ot r i a n g l ea sas u b g r a p h as p a n n i n g p a t h ( r e s p e c t i v e l y , s p a n n i n gc y c l e ) i so f t e nc a l l e da h a m i l t o np a t h ( r e s p e c t i v e l y , h a m i l t o nc y c l e ) w es a yt h a tag r a p hi sh a m i l t o n i a ni fi ta d m i t sah a m i l t o n c y c l e a n dh a m i l t o n i a n c o n n e c t e di fi tc o n t a i n sah a m i l t o np a t hc o n n e c t i n ga n y t w op r e s c r i b e dv e r t i c e s 2 c h a p t e r1 i n t r o d u c t i o n ag r a p hgi sb i p a r t i t ei fi t sv 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 s xa n dys ot h a te v e r ye d g ei ngh a so n ee n di nxa n dt h eo t h e re n di ny i f e v e r yv e r t e xi nx i sa d j a c e n tt oe v e r yv e r t e xi ny ，t h e ngi sc o m p l e t eb i p a r t i t e w ed e n o t eb yk m 竹t h ec o m p l e t eb i p a r t i t eg r a p hgw i t hb i p a r t i t i o n ( x ，y ) s u c h t h a tl x l = ma n di y i = n l e tgb eag r a p h f o ra n ys v ( g ) ue ( g ) ，d e f i n eg st ob et h e s u b g r a p ho fgw i t hv e r t e xs e tv ( a ) 一( sny ( g ) ) a n de d g es e t e e ( g ) ： egso rei sn o ti n c i d e n tw i t ha n yv e r t e xi ns ) l e thb eas u b g r a p ho fg w e d e f i n eh + sa st h eg r a p hw i t hv e r t e xs e tv ( h ) u ( sny ( g ) ) a n de d g es e t e ( h ) u e e ( g ) ：e sa n d ei si n c i d e n tw i t ht w ov e r t i c e si nv ( h ) u ( sn y ( g ) ) ) w h e ns = _ s ) ，w es i m p l yw r i t eg 一8a n dh + s i n s t e a do fg 一 s ) a n dh + s ) a g r a p hg i sc a l l e dc o n n e c t e di fa n yt w oo fi t sv e r t i c e sa r ej o i n e db yap a t h i ng ；o t h e r w i s e ，i ti sd i s c o n n e c t e d am a x i m a lc o n n e c t e ds u b g r a p ho fgi ss a i dt o b eac o m p o n e n to fg w es a yt h a tgi s 尼一c o n n e c t e d ，w h e r eki sap o s i t i v ei n t e g e r ， i fi y ( g ) i ka n dg si sc o n n e c t e df o re v e r ys u b s e ts v ( c ) w i t hi s i 6 i n2 0 0 4 ，c h e n ，f a n ，a n dy u 8 p r o v e dt h a te v e r yn v e r t e x4 - c o n n e c t e d p l a n a rg r a p h h a sac y c l eo f l e n g t hkf o re a c h 七n 一4 ，n 一5 ，n 一6 ) w i t hk 3 8 c h a p t e r1 i n t r o d u c t i o n t h i sw o r kw a sp a r t i a l l ym o t i v a t e db yac o n j e c t u r eo fm a l k e v i t c h 【3 9 ，w h i c hs a y s t h a ti fa n 扎一v e r t e x4 - c o n n e c t e dp l a n a rg r a p hgc o n t a i n sac y c l eo fl e n g t h4t h e n gc o n t a i n sac y c l eo fl e n g t hkf o re v e r y 忌n ，n 一1 ，3 ) i nc h a p t e r2 ， w ef u r t h e rs h o wt h a te v e r y4 - c o n n e c t e dp l a n a rg r a p ho fo r d e r 几( w i t h 扎1 0 ) a d m i t sac y c l eo fl e n g t hn 一7 1 2 4o t h e rr e l a t e dp a p e r s ak - w a l ki nag r a p hgi saw a l kp a s s i n gt h r o u g he v e r yv e r t e xo fga tl e a s t o n c ea n da tm o s tkt i m e s ac i r c u i tg r a p h ( g ，c ) i sa2 - c o n n e c t e dp l a n eg r a p h gw i t ho u t e rc y c l ecs u c ht h a tf o re a c h2 - c u tsi ng ，e v e r yc o m p o n e n to fg s c o n t a i n sav e r t e xo fc i ti si m m e d i a t et h a te v e r y3 - c o n n e c t e dp l a n a rg r a p hg i sac i r c u i tg r a p h ( w em a yc h o o s ect ob ea n yf a c i a lc y c l eo fg ) i n1 9 9 4 ，g a o a n dr i c h t e r 2 6 】p r o v e dt h a te v e r yc i r c u i tg r a p hc o n t a i n sac l o s e d2 - w a l k t h e e x i s t e n c eo fs u c haw a l ki ne v e r y3 - c o n n e c t e dp l a n a rg r a p hw a sc o n j e c t u r e db y j a c k s o na n dw o r m a l d 3 4 g a o ，r i c h t e r ，a n dy u 2 7 e x t e n d e dt h i sr e s u l tb y s h o w i n gt h a te v e r y3 - c o n n e c t e dp l a n a rg r a p hh a sac l o s e d2 - w a l ks u c ht h a ta n y v e r t e xv i s i t e dt w i c ei si nav e r t e xc u to fs i z e3 ( c o n j e c t u r e db yt h o m a s ) a no u t e rp l a n a rg r a p hi sap l a n eg r a p hs u c ht h a ta l lv e r t i c e sl i eo nt h e i n f i n i t ef a c e i n1 9 9 5 ，t h o m a s s e n 5 6 u s e dt h et u t t es u b g r a p ht e c h n i q u et o e d g e - p a r t i t i o nap l a n a rg r a p hi n t oa no u t e rp l a n a rg r a p ha n d a b i p a r t i t eg r a p h t h i sw o r kw a sr e l a t e dt oa no l dc o n j e c t u r eo fc h a r t r a n d ，g e l l e r ，a n dh e d e t n i e m i ( s e e 7 】) t h a te v e r yp l a n a rg r a p hc a nb ee d g e p a r t i t i o n e di n t ot w o o u t e rp l a n a r s u b g r a p h s t h em a x i m u mb i p a r t i t es u b g r a p hp r o b l e mo nag r a p hgi st h a to ff i n d i n ga b i p a r t i t es u b g r a p ho fg w i t ht h em a x i m u mn u m b e ro fe d g e s t h o m a s s e n 5 7 r e c e n t l yp r o v e d ，u s i n gt h et u t t es u b g r a p ht e c h n i q u e ，t h a ti fg i sa3 - c o n n e c t e d c u b i ct r i a n g l e - f r e ep l a n a rg r a p ht h e ngc o n t a i n sab i p a r t i t es u b g r a p hw i t ha t l e a s t 业2 型4 一吾e d g e s t h o m a s s e n 5 7 a l s op r o v i d e da c l a s so fg r a p h ss h o w i n g t h a tt h ec o e f f i c i e n t 面2 9c a n n o tb ei m p r o v e dt om o r et h a n 丽4 7 i nc h a p t e r3 ，w e e x t e n dt h o m a s s e n st e c h n i q u eb yp r o v i n gs t r o n g e rr e s u l t so nt u t t ec y c l e sa n d i m p r o v et h i sl o w e rb o u n dt o 兰业3 2 倒一丽9 9 c h a p t e r2 c y c l e si n4 - c o n n e c te dp l a n a rg r a p h s i nt h i sc h a p t e r ，w ep r o v et h a te v e r y4 - c o n n e c t e dp l a n a rg