（应用数学专业论文）k连通图中的可收缩团.pdf

摘要 摘要 连通图g 的一条边或一个子图是如可收缩的，如果这条边或这个子图收 缩后所 ! 导的图仍是连通的。图的团是指图中极大的完全子图。t u t t e 证明了下 面著名的结果：任意顶点数大于或等于5 的3 一连通图都含有一条3 可收缩边。c 皿0 m 解s 髓证明了任意不含三角形的自连通图都有一条后可收缩的边。这里的三 角形是指长为3 的圈。k 矗w 锄b a y a s h i 证明了对于某个整数4 ，任意的k 一连通图 或者含有共享一条边的两个三角形，或者含有一条可收缩的但不包含在任何三 角形中的边，或者含有一个一可收缩的但不与其它三角形共享条边的三角形。 显然， 盈w a 糟b a y a s h i 的结果包含了c t h o m a s s e n 的结论。t u t t e 、k 舢b a y a s h i 和t h o m a s s e n 等人的研究只是侧重于七连通图中顶点数比较少的可收缩子图的存 在性，如边或者三角形另外一些研究者则对连通度作了限制，一般研究3 一连通 图、4 连通图、5 连通图、6 一连通图还有一些学者则是侧重于一类对了图有限制 的连通图的可收缩边的研究。在这篇论文里，我们研究了连通图中子图的顶点数 比较多时- 可收缩子图的存在性。结果表明这种可收缩子图的存在性依赖于共享一 条边的三角形的数目。我们推广了k a w a r a b a y h i 的技巧，并证明了一个更一般的 有关可收缩团的结论。 我们证明了对于t o 和瑚x 4 ，t + 3 ) ，任意连通图g 或者包含有一个顶 点数最多为t + 2 的可收缩团，或者有一条边包含在g 的t + 1 个三角形中，或者存 在g 中的两个团至少共享一条边，或者图g 中有一个顶点数大于或等于4 和一个顶点 数大于或等丁3 的团，它们的交是非空的。 本论文分为以r 四个部分：在第一章里，我们给出了本文所用到的一些相关的 图论定义，并且回顾了连通图中k 可收缩子图这个问题的背景和已有的结果；在 第二章里，我们给出了本文的主要定理，并且指出该定理是1 m t e 、k a w a r a b a y 嬲h i 和c t h o m s e n 等人所做结果的推广；在第三章里，我们给出了证明主要定理所需 的四个引理以及它们的证明；在第四章中，我们给出了主要结论的完整证明过程。 关键字：连通图团可收缩子图可收缩团 a b s 仃a c t a b s t r a c t a ne d g e ( ) ras u b g r a p h ) i na 知嘣蛐l e c t e d 鲫hi s 七- c o n 仃a c t i b l ei fi 乜c o n 仃a c t i o n 坤s l l l t si na 一c o n n e c t e d 伊印h ac l i q u ei nag r a p hi sam 积j m a lc o m p l e t cs u b g r a p h n i s w e uk n o w n 也a t “e r y3 唰砌1 e 鼬c d g r a p ho f o r d 盯5o r m o r e 洲璐a3 - c o n t r a c t i b l e c d g e t h i sr e s u i t i sd u e t ot u 慨k a w 砌a y 勰h ip r o 、倒t h a t f o r 如y i n t e g e r 南24 ，e v e r y 知一c o 皿e c t e d 簪a p hc o n t a i n st w o 域锄g l e ss h 撕n g 蛆e d g e ，o ra d m i t sa 耙- c o 删b l ee d g e n o tc o n 协i n e di na l l yt r l a n g l e ，0 ra d m i t sa 肛c o n n 砌i b l c 研彻9 1 ew h i c hd o e sn o ts h a r e 她 e d g ew i 也a n yo 也e r 试a n g l e a 试锄g l ei sa 斜c l eo fk n g i h3 勋：w m b a y a s h l st h e - 蝴ni m p l i e st h o m a s s e n s 犯s u l tl h a t 昏懈r y 缸i 舳9 1 e 一厅c e 七一c o 皿e c t e dg r a p hc o n t a i n sa 缸c o b l ee d g e 1 、执，k a w a r a b a y a s h i i n 衄dn 唧n a 鼹吼s 蛳l d i 懿f o c l l so na 碡e x - i s t 衄c eo f a 七一c o n t r a c t l b l es u b g r a p ho f s m a l ls j z ei na 掣印hs u c h 鹊e d g e s0 r 研a n g l e s ，锄d o 也盯p e o p l e ss t u d i e dt h ee x i s t 铋o fc o n 拓a c t m l es u b 簪a p h sc a n c e 嘶n g 也ec o 衄e c 咖姆 o f g i nag e n e r a lw a y f h e yc o n s i d 盯3 - c 咖e c t e d 乒印h s ，4 c o n n e c t e d 鲫h s ，5 一c o n n e c t e d 笋a p h s ，锄d 6 c o n n e c t e d 簪a p h s s o m e o t h e r 他l 砷e d r c a r c h c o 础掰试n g c o m r a c “b l e e d g e s i n ”s 雠c t c dc l a s s e so f 掣印h sh 鹅b e d 0 雎ht h i sp 印w ca i mt oi n v e s t i g a t et h ec x i s t c eo fa 七- c o 毗孢c t i b i c 铷b 蓼a p ho f l a r g eb i z ei na 岛一c o 皿e c t c d 铲a p h i tt i 瑚蕊o u t 也a t m ee x i s t e n c eo fs u c hs u b 鲫h sd 印e n d s t h en 呦b c ro fm 姐9 1 e ss h 撕n gac o m m 彻 c d g e w 色e x t e n dk l w 缸a b a y a s h i st e ：h n i q u ea n dp 坩v cam o r eg e n c r a lr e s u l tc o n c e m i n g 后- 仃a c t i b l ec l i a u e s w ep r o v e l h a t f o r oa n d 七m 瓢 4 ，t + 3 ) ，州e r y 七一c 0 皿c c t e dg r a p hc o n t a i n sa 七一c o n 订a c t i b i ec 1 1 q u eo fs i z ea tm o s t + 2 ，o rt h e r ei sa ne d g ec o n t a i n e di nt + 1t r i 锄g i e s o f g ，o r t l l e r ee x i s t t w oc l i q u e s i n gs h a r i n ga t l e 觞t o n ee d g e ，o r t h e r ee x i s t i n gac l i q u e o f s i z ea t1 e a s t4a n dac l i q u eo f s i z ea tl s t3w h o s ei m e r s e c t i o ni sn o n e m p 够 1 1 1 l st l l e s l si so r g a n i z e da sf 0 1 l o w s bc h a p t c rl ，w er e v i 哪t h eb a s i cd 娟n 讹n s 粕dl h eb a c k 伊o u n do f 屉- c o n 仃a c t i b l es u b g r a p h si n 七c o 腿c c t e dg r a p h s i n 西印t e r2 ，w e d i s c i l s st 1 1 em a l nr e s u l to ft h l sp 印c r ，w h i c hi st h eg e r a l i z a t i o no ft i m e ，t h o m 嚣s c n 粕d k a w a r a b a y 硒h i sr c s u l t mc h a p t 盯3 ，w eg i v ef o wb 丑m 船舶dt h ed e 忸1 1 s i nc h a p t c r4 ， w e g i v ct b ec o m p l e t ep r o o f o f t h em a i nr e s u l t k e yw o r d s ：七一c o n n e c t e dg r a p h s ，c l i q u e s ，c o 咖c t i b l es u b g m p h s ，c 仃a c t i b l ec h q u e s n 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：点一之 上彬f 年j ，月嵋日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 哆一乓 解密时间：年月日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名： 名矗 州年，玛| 2 琶 c h a p t e r 1 i n t i o d u c t i o n i nt h i sc h a p t e rw e 矗r s tr e c a l ls o m et e m i i l o l o g i e s 锄dn o t i o i i s ，锄dt h 姐g i v ct h eb a c k 霉o u n do ft h et h e s l s 1 1p r e u m i n a r i 鹳 w e f 0 j l o w b o n d ya 1 1 d m u r i y 【6 1 f o r t i l e n o 诅t i o n s n o t d 荫n e d h e r e ，如d c o 璐l d c r s i m p l e 铲a p h so n b i e ，a l lg r a p h sc o n s i d e r e da r e 矗n i t e ，u n d i r e c t c da n d1 0 0 p l e s s l 醣凳b ea n i n t e g e r ，a 罄a p h i s k c d 珊鲥e d i f i t h 鹊a t l e a _ s t k + l v e m c e s 粕dc o n t a l n s v c r t e xc u to fs l z es m a l l e r 也髓七a ne d g e ( o ras u b 鲫h ) i na 七- c o 皿e c t e d 旷印hi s 知一c d 肋w “f 6 居i f l t sc ( m t m c t i o nr e s u l 拓ma 七一c o n n e c t c d 鲫h 1 m ec o n t 哪t i o no fa i le d g e i na 酽a p bi st oi d e n “母t h e 咖v e n i c e so f t h ee d g e 锄dt od e l e t ca i lr c s u l t i n gl o o p s 柚d m u n i p i ee d g e s ac n 叮“pi na 鲫p hi sam 都【i 埘i a lc o m p l e t cs u b g r a p h ，锄dac l i q u eo fs l z c t i sc a l l c da n 蛔纰l 就gb ea 铲a p h w bu y ( g ) ，e ( g ) 勰d6 ( g ) t od e 埘眦也e v c r t c xs 鸭e d g es e ta n dn l em i n i m 砌d e g r c eo f g ，r c s p b v e l yf 0 ra n y $ y ( g ) ，g ( z ) d e n o t t h e n e i g h b o t h o o do f z i n g ，趾dd o t e b yd g ( 茹) = 0 ( z ) 1 1 h ed e g r e eo f z j n g 撕日b eas u b g r a p ho f g t h g ( 日) d c n o t c s 也es c to f v e n i c c so f g y ( 日) e a c ho f w h i c hi sa d j a c e n tt oa tl e 船tav e n e ) 【i ny ( 日) ，w h e n 日i sc o n n e c t e d ，w eu s e g 日t od e n o t et h eg r a p ho b t a i n e d 矗f o mgb yc o n 乜a c t i n g 日a l ，f 研姐ye e ( g ) ， w eu s e g 已t od c n o t e t h eg m p ho b t a i n c d 丘o m g b yc o n t r a c t 吨e 1 1 1 e 弘埘o f 鲫h s g a n dg ，w i t hd l s j o i n tv e r t e xs e t sy ( g ) ，y ( g ) ，e d g cs e t se ( g ) 粕de ( g ) i st l l e 舒a p hw l t h y y ( g ) u y ( g ) a l l d e = e ( g ) u e ( d ) 【8 】撕g + g ，d e n o t e 山e 弘加o f g a n d c h a p t e r1 i n 廿0 d u c n o n t h e r ea r es o m en o t i o n su s e d i n t h ec i t e d 也e o r 吼s a ，f ，坩卿厅i s t h eg r a p hh a s v 吼i c e s c o 玎e s p o n d l n g t o t h e e d g c s o f g ，粕d 咖v c r t i c 龆a r c j o m e d b y 弛e d g e ，w h e n e v c r ( h e c o r r e s p o n d l n g e d g e s o f g a m a d j t 【8 】三船动i sa l s oc a l l e d 加把，曲口阿俨g 仡妒 1 1 l ej g 聊o f ag r a p hg i st l l eg r a p ho b t a i n e d 劬mg b y j o i n i n ge v e r yp a i ro f v e n i c e s w h o s ed i s t a n c e i n g i s2 8 】撕暖d a t c 血c 凹獬mo f 也ec y c l e q a “6 l c g 泖 i sar e g u l a rg r a p ho f d e 铲3 【8 】1 k 司舰础口黼即删纱o f g i sd 而n c d 船t h e n 啪b c fo fe d g e st h a tm u s tb ed e l e t c d 丘d mgt od i s c o 衄e c tac o m p o n e n ts ot h a te v e l y r 咖a i n i n gc o m p o n c n tc o n t a i mac y c k 【8 】gi sq 肥f i 伽砂一e 如争埘e c 耐i ft h ec y c l i c c d g e c 0 如e c t i v 竹o f g i sa t l e a s t 七 8 】i f g d 0 n o t h a v e a 七一c o n 伽i c t i b l e e d g e ，t h e n g l s s a i dt 0b ec d f 朋c f f d 胛c 一，f c 口咖七一c o m ，卵f b d 叼 af r f 口押g 怡l sac y c i eo f l 朗g c h3 【7 】ag r a p hi sc a j l e df 砌馏拓咖pi fn oi n d u c e d 弧b 鲫p hi sa 耐a n g l e 【8 】 1 2b a c k g r o u n d t u t t e 【2 0 】i n 劬d u c c dt h ec o n c e p to fac o n 仃a “b l ec d g e ，粕ds h o w e dt h a ti fg i sa 3 c o n n e c t e d 鲫p ht b c l lg = 甄o rg c 伽t a i 璐a3 - c o n 虹a c t i b l ee d g e 1 1 l i sr c s u hi su s e d t 0s h o wm a ta l i3 - c o n n e c t e dg r a p h sc 柚b eo b 诅i n e d 疗o m 耳4b yt w os l m p i eo p e r a t i o n s b u t1 1 1 0 m a s s e n 19 】s t a t 甜t h a tt 1 1 e 强随i 而n i t e l ym a n y 七一c 0 皿e c t e d 七- r e g u l a rg r a p h s w h i c hd o n o t h a v e ac o 蝴c t f b l c c d g e f b r 七4 m t h es 鼬c p 印t h o m 鼬s p r o 、，e d 也e f 0 1 l o w i n gt l l e o r c m t h e o r e ml l ( t h o m a s s e n 【1 9 】) l c tgb ca 七吒。舢e ：t e d 研锄9 1 e 一缸e 脚h t h gc o n t a i 地me d g ees u c hi h a tt h e c o i l t r a 州0 no f er e s u l t s i na 一c 0 衄c c t e d 舯p h 汕俳k 岛汹f 矾i 胁4 ) ho 也e r 、加r d s ，t h o m 鹤s s h o w c dt h a tf b r 膏4 c v e r y 七一c o 船e c t c dg r a p hc o n t a i n s a 试柚g l eo ra d m i 协a 一c o n n a c t i b l ee d g c 1 h sr 船u n w 鹤t h 锄璐c d i n 【1 9 t 0p i o v ea c o n j e c t u r eo f i ，o v 矗s z e g a w a 1 i 】s t u d i e dt h em i n j b 哪d e g r c e c o n d i t l o nf b ra 七一c 0 皿c c t c d 鲫ht 0h a v ca c 仃i l c t i b l ec d g e ，h ep r o v e dt h ef o l l o w i n gt h e o r 锄 2 c h a p t e r1 h 仃0 d u c t i o n t h e o r e m1 2 ( l g a m 1 1 】) l e t 后2b ea n i n t e g e r ，柚d l e t g b ea 七一c 0 皿e c t e d g 髓p h w 曲d ( g ) 譬t h c i l gh a sa 七一c o n 仃a c t i b i ee d g c ，u n l e s s2 后3 翘dgi si s o m o f p h i ct o l ， k r i e s e l l 1 7 】e x t e n d c de g a w a st h e o 衄锄dp r o v c d 也ef o l l o w i n gd e g r e es u mc o n d i 廿o nf 研a 一c o n n e c t e ( 1 舯p ht oh a v ca 一c o n 仃a c t i b ke d g e t h e o m m1 3 ( k r i e s e l i 【1 7 】) l c t 七2b ea n i n t e g 姐d l e t gb ean o n c o m p l e t c 七一c 0 衄e c t c d 孕a p h i f d g ( z ) + d g ( 可) 【譬jf o ra n yp a i ro f d l s t i n c tv 枷c 部矗暑，o f g t h c ng h 勰a 七一c 蝴n b l ee d g e e g a w a 武“ 9 1p r o v e d t h e f o l l o w i n g t h e o r e m ，觚dg i v c 也cu 印盯b o u n d c d f o r t h c 瑚m l b 髓o f 凳一c o n t r a c t b l ee d g e s t h e o r e m1 4 ( e g a w a 跣以 9 】) l c t g b e a 七一c o n n e c t e d t r i a n g k 一曲e g m p h t h e n g c o n t a i n s m a x l 矿( g ) i + 警一3 七，i e ( g ) 1 ) n t r ，l c t j b l ee j g c s a st h e o r c m1 4s h o w s ，a 七c 0 衄c c t e d 砸a n 出e 丘e eg r a p hl l a sa1 0 to f 七- c o n t r a c t i b l e e d g e s h e n c et h ec o n d i t i o n 仃i 舳9 1 e 一矗e e ”i st o os n d n g k 蠡l c t ，k a w a 均b a y a s h i 【1 4 】 p r o v e dt h ef o l l o w i n gt h e o r e m l c t 耳；b e 血e 铲a p ho b t a i n c d 丘彻1 墨。b yr c m o v i n gj u s t 加e e d g e ，w h e r c n i s a n i m e g e r t h e o r e m1 5 ( k a w a r a b a y a s h i 1 4 】) l c t 七3b ea n o d d m t e g e r ，a n d l e t g b e a 竞c o 皿e c t c d t h a t d o e s n o t c o n t a i n 竣。t h 衄g h 嬲a 一c o n 仃a c t i b l ee d g e s o m eo t h e rr e l a t e dr e s e 牡c hc o n c 啪i n gc o n 仃a c t i b l ee d g e si nr e 嘶c t e dd 鹬s e so f g r a p h sh a sb e e nd o n ei n 2 】柚d 【3 】 佗s p c c d v e l y 1 n 【2 】，a n d 0 ，k g w a m b a y a s h ip r o v e d t h ef o l l o w i n gl w ol h e o r e m s t h e o m1 6 ( a n d o ，k a w 盯a b a y a s h i 2 】) l 既七，8 柏d 铀ep o s l t i v e i l l t e g e 璐姐c h t h a t 七5 粕ds 0 1 ) 七i f a 七一c 锄e c t e d 掣a p h gh a s 船i 血e r 鲍+ 8 致n o r 尬+ t 鲍t h 既g h 嬲a c o 咖c t i b l e c d g e t h e o 他m1 7 ( a n d o ，k a w 姗b a y a s h i 2 】) 。 l e tgb ea 七一c o 哪e c l c d 鲫ht h a tc o n t a i n s i t h e r 蚝n o r5 鲍+ 马w i 也七5 i f 3 6 ( g ) 七+ 1 r r h e n gh 勰a c o 吮c t i b i e e d g e ( w h e r c b d e n o t c s l h e p a h o f l e n g i h3 ) 州3 】a 1 1 d o ，k a n e k o 趾dk a w 砌b a y 豁h ip r o v e d 也ef o l l o w 崦r e s u l t t h e o r 哪1 8 ( a n d o ，k a n e l ( oa n dk a w a r a b a y a s h i 【3 】) i fa 詹c 0 埘e c t c dg 。a p hw i mn o ：d o e sn o th a v ea 七一c 0 咖c t i b l ee d g e t h e n 七i se v e n 姐d e a c h v e n e x l n gi sc o n t a i 船d i na t k a s t 铆。仃i 缸g l e s t h ef o l l o w i n gs e v e r a lr e s u 蛔c c c mt h ec o n t m c t i b l e 酣g e so f 锄a l lc o n n e c t l v j t y 鲫p h ss u c ha s3 ，4 ，5 ，6 - c o 皿e c t e d 掣a p h s a 七c o n n c c t e d 卿hg i ss a l dt 0b e 疗。仃一段 七一c o 棚8 c 把d 聊 i f t h e r c i s n o i n d u c e ds u b 掣a p h i s j 矗 m 【1 】，a n d o ，e n o m o t o 勰ds a i t op r o v c dt h ef o u o w i n gt h e o f e m t h e o 代m1 9 ( a n d o ，e n o m 咖锄ds a i t o 【1 】) e 唧n o n 段3 - c o n i l e c t c d 鲫h gh a sa t l 删世掣c o n 仃a c 曲l e e d g e s h l 【1 2 ，e g a w a ，o t a ，s a “o 彻d lp r o v c d 也ef o u o w i n gt h e o 他m t h e o r e ml 。1 0 ( 1 1 9 a w a o t a ，s a i t oa n dy h 【1 2 】) l c c p 5b ea n i n t c g e lt h e n f o r “e r yn o n 甄3 一c o 姗e c t c d 鲫h go n pv e n i c e s t h e m n b e ro f n o n c o n t r a c t i b l ee d g e si sa tm o s t 3 p 一【i ( 、互甭r 千固一5 j n o n c o n l m c t i b l ee d g e s ( 1 i k cc o n 仃a c t i b l cc d g e s ) h a v eb e e 璐e di ns e v e r a lp 印e r s ，f o r e x p l e ， 4 】a n ( 1 211 ，、v eo m i lt h ed e t a i l s t h o s e 4 一c o n n e c t e d g m p h s w i t h o u t 4 c o n n a c t i b l e e d g e s w e r c c h 啪c t e r i z e d i n 【1 3 】柚d 【l 司 i n 1 3 卸d 1 8 】f o n t e t ，i n d 印e n d e m l y ，m a n i n o vp r o v c dt h cf o l l o w i n gt h e o 煳 t h r e m1 1 1 ( 1 1 0 n t e t 【1 3 】，m a n m o v 【18 ) l c tgb ca4 一c o n n e c t c dg f a p h ，i f gd o e sn o tc o n t a 妞a4 - c o n t f a c t i b l ee d g e ，t h e ngi se i t h c r 锈( t h es q u a r co f c y c l eg ) o r t h el 疵8 呷ho f ac ) ，c l i 翻1 y4 - e d g e c n e c t e dc u b i cf a p h 飚y o s h i 以以 1 6 】p m v e d 也ef o l l o w i n gt h e o r 咖c o n c e i n i n g5 - c o 衄e c t e dg r a p h s t h r e m1 1 2 ( kj y o s h ie t 口z 【1 6 】) l dgb ea5 一c o n n e c l e d 伊a p hm a td o e sn o th a v ea5 - c o n t r a c t i b l ee d g e t h e ne a c hv e r t e x o f g i sa d j a c e n t t 0a t i e a s t o v e n e x o f d c 铲5 4 1 1 1 0 s e6 一c m n e l 【e dg r a p h sw i 也o m6 一c o n 仃a c t i b l ee d g e sw e r cc h 啦c t e r i z e di n 【5 】 t h e ) rp f o v e df 0 1 l o w i n gr e 蛐t s t h e o 忡m1 1 3 ( k a n d o ，a k m e k 0 缸dk k a w 啪b a y a s h i 5 】) l c t g b e a 6 c o n n e c t e d 鲫h t h a t d 0 韶t h a v ea 6 - c o n n a c 曲k c d g e n g h a sa t k a s t ；1 v ( g ) lv c n i c e so fd e g r c e6 e x t e n d i n gt e c h n i q u e so f e g a w a 【l o 】，k 删旧船b a y 硒h i 1 5 】i m p r d v e dt h o m a s s e n sr e s u i tb ys h o w m gt h a tf 研七4 ，e v e r y 七一c o 皿e c t c d 黟a p hc o n t a i m 似。仃i a n g l e ss h a r i n g m e d g e ，o ra d m i t sak c o n t r a 吐i b l ce d g en o tc o n _ t a j n e dj na n y 伍a n g l e ，o ra d r n i t sak c o n 仃a c t i b l et n a n g i ew 1 1 i c hd o e sn o ts h a r e 孤c d g e 诵也蛆yo t h e r 仃i 彻g l e n o t et h a tl f t w oc l i q u e ss h a r ca ne d g em e nb o t hd i q u e sa r eo f s i z ea tl e a s t3 w 1 t l it h i s n o 嘶0 n ，k 咐甜a b a y a s h i st e s u l tc 孤b es 铆e d 私f o l l a w s f 0 ra n yn c g e r 七4 ，e v e r y 晃- c 0 皿e c t e dg r a p l lc o n t a i n st w o 仃i 卸唔l e ss h a r i n g 雒e d g e ，0 ra d m “sa 七一c o n 仃a c t i b l e2 一d i q u e f b rs o m e2 l 3 n e x tc h a p t e rw ew i l lg 髓“硌w w a b a y h i sr e s u i t 5 竺! ：! 旦堕! ! ：垒望! 苎翌坚兰型2 竺堕垦竺堂型竺望! 里! 塑堡璺 c h a p t e r 2 ag e n e r a l i z a t i o no f k a w a r a b a y a s h i st h e o r e m i nt h i sc h a p t e rw cg i v et h em a i nr e s u l to f t h et h e s is 2 1 k a w a 瑚b a y a s h i st h e o r e m e x t e n d i n g 【e c l l n i q u e so f e g a w a 1o 】，勋w a f a t a y a s h i 【1 5 】i l l l p r o 、，e d1 1 1 0 m a s s e i i s 静 锄nb ys h o w i n gt h a tf o r 七4 c 、，e r y 七伽e c t e dg r a p hc o n 协i 璐t w o 仃i 锄g i e ss h a r i n g a ne d g e ，o ra d m ha 惫c o n 仃t i b l ee d g en o tc o 地d j n 锄y 城a n g k ，0 ra 出n “sa 南- c o n 咖c t i b i e 仃l a n g i et h a td o e sn o ts h a r ca nc d g ew i t h 龃yo t h c f 埘粕翻e t h e o r e m2 1 ( k a w a f 曲a ) r a s h i 【1 5 】) l 既七辱b ea n i n t e g e l a n d l 豇g b ea 七一c o 皿e c t e dg r a p h t h a td o e sn o tc o n t a i n 酊1 1 1 朗 t h c r e 酝i g t sa 一c o n t t a c t i b l ce 始cw h i c h i s n o tc o n t a i n c d 缸a n y 仃i a n 9 1 c0 r t h e r ee x i s t sa 七- c o n t r a d i b l e 仃i a n 9 1 e f r o ma b o v cd i s c u s s i o n s 船dk 抓，a f a b a y 粥h i st h e o 垧吼w ec 觚s e em a tt h e i rr c s u l 协 a 1 i n o s tc o n c e mo ns u b 舯p h so fs m a l ls i 粥s u c h 镐e d g e s 甜仃i 觚g i e s o nt h eo t h c rh a n d ， t h ec o n d i t l o no ft h ee x i s t c i l c co fk c o n 仃a c t m ks u b g m p h sbt o os 虹o n g n e x ts c c t i o nw e w l l lg i v eag e n e r a l i z a c i o no f k 丑呦b a y 嬲h i st h c o r e 觑 6 l c h a p t e r2 ag e r 虹珊n o no f k a w 啪b a y h i st h c o r c m 2 2ag e n e r a l i z a t i o no fk a w a r a b a y a s 量i i st h e o r e m w ea i mt 0i n v e 甜i g a ：c et h e 懿j s 吣o fa 靶一c 0 d 主r a c t i b kg u b 蓼a p h “k b 既s l z eha 毛一 c o 加e c t t 斑掣叩h i tt u i 璐o u td l a tt k 既i s t c n c eo f8 u c hs u b g r a p h sd c p e l l d s0 廿t h en u m b 盯 o f 缸i a n g l e ss h a n n gac o m m o ne d g e w c 缸ea b i et om o d i 母k a w 盯a b a y 淞h i sm e t h o d 锄d p r o v et h ef o i l o w j n gm o r cg 髓e 珀h s t l l t t h 时啪2 2 ( g 肋e r a h 删i o n0 f k 删眦b a y a s h i s t h e o r 吼) 撕t 0a i l d 七2 m a x 4 ，t + 3 e i n t c g 粥，犯d l c t g b c8 七伽e c t e d g r a p h t h 朗o n e o f t h ef o l l o w i n gf e s u l l sh 0 1 d s ( 2 2 1 ) t h e r e i sa n 酣g e c o n 协i n c d i n t + 1 舡i 龃g l e s o f g ( 2 2 2 ) t h c r cc x l s tt w oc l i q u 韶i ngs h a r i n ga tl c 解ta e d g c ( 2 2 3 ) t h e r ee x l s t i n g ac l l q u e o fs i a t l e 勰t 4a i l dac l i q u e o f s i z ca t l e a s 3 w h o s e i n t e r s e c t i o ni sn o n - e 1 1 l p 咿 ( 2 ，2 4 ) t h e r e i sa 七一c o n 仃a c t i b l ec l i q u e i n g o f s i z ea t m o s t t + 2 w h e nt = 0a n dg i s 埘粕g