（运筹学与控制论专业论文）定向图的直径和平面图的不完全选色性.pdf

学位论文独创性声明 本人郑重声明： 1 、坚持以”求实创新一的科学精神从事研究工作 ! 、本论文是我个人在导师指导下进行的研究工作和取得的研完成 栗 3 、太论文中除引文外，所有实验、数据和有关材料均是真实的。 4 、本论文中除引文和致谢的内容外，不包含其他人或其它机构已经 发表或撰写过的研究成果 j 、其他同志对本研究所做的贡献均已在论文中作了声明并表示了谢 意 作者签名：盘趣垃 日期：奎堕： 学位论文使用授权声明 本人完全了解南京师范大学有关保留、使用学位论文的规定，学校有 权保留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸 质版；有权将学位论文用于非赢利耳的的少量复制并允许论文进人学校 图书馆被查阅；有权将学位论文的内容编人有关数据库进行检索，有权将 学位论文的标题和摘要汇编出版。保密的学位论文在解密后适用本规定。 作者釜名：盘应墼篚 置期：婴：l ab s t r a c t f o rag r a p h 日( m ，n ) = k nvk t ，l e t 日7 ( m ，n ) d e n o t ea no r i e n r a t i o no f 日( m ，n ) h a v i n gm i n i m u mf i n i t ed i a m e t e r d e f i n e ( 仇，咒) = d i a m ( h ( m ，佗) ) w h e r em22a n dn 1 i nc h a p t e r1 ，w ew i l lp r o v e t h ef o l l o w i n gr e s u l t s ：f 1 ) f o rm = 2 p4 - 1 ，p 1 ， ( m ，他) = 2 w h e n e v e rn ( 1 霉j ) 一ma n d ( m ，n ) = 3w h e n e v e rn ( 【m 罟j ) - ( 2 ) f o rm = 4 p + 2 ，p 0 ，i fns ( 里) 一罟，t h e n ( m ，n ) = 2 ；o t h e r w i s e ( m ，n ) = 3f o rm = 4 p ，p l ，i f 礼( m 罢) 一警一1 ，t h e nh ( m ，佗) = 2 ； o t h e r w i s e ( m ：n ) = 3 w ea l s od i s c u s sd e f e c t i v ec h o o s a b i l i t yo fp l a n a rg r a p h si nc h a p t e r 2 ag r a p hgi sc a l l e d ( 七d ) 4 一e h o o s a b l ei ff o re v e r yl i s ta s s i g n m e n t ls a t i s f y i n gi l ( 钉) i = 岛f o ra l lu 1 旷( g ) ，t h e r ei sa n 三一c o l o r i n go fg s u c ht h a te a c hv e r t e x6 fgh a sa tm o s tdn e i g h b o r sc o l o r e dw i t ht h e s a m ec o l o ra si t s e l f il e tgb eap l a n a rg r a p ho fg i r t hn o tl e s st h a n 4a n dc o n t a i nn o5 。a n d6 - c i r c u i t s i ft h en u r n b e ro f4 一c i r c u i t si sn o t m o r et h a n4 ，t h e ngi sf 2 ，2 ) c h o o s a b l e i ft h en u m b e ro f4 - c i r c u i t s i sn o tm o r et h a n5 ，t h e ngi s ( 2 3 ) 4 c h o o s a b i e k e yw o r d s ： i k 1 i n i l n m nd i a m e t e r o r i e n t a t i o n g i r t h ，p l a n a r g r a p h d e f e c t i v ec h o o s a b i l k ) ? 摘要 对于图日( m ，n ) = k 。v ，给图定f 句使得它的直径最小这里 t 2 和n 1 时，我们有这样的结论；( 1 ) ( m 是奇数时) 对于t n , = 2 p + 1 ， p 1 这种情况，当几( 霉1 ) m 时图的直径是2 ，当n ( i 霉1 ) 时 候是3 ( 2 ) ( m 是偶数时) 对于m = 4 p + 2 ，p 0 这种情况，如果 n ( 翟) 一罟，那么直径是2 ，其他的时候是3 ；对于t 7 , = 4 p ，p l 这 种情况，如果九( 竺) 一罟一l ，那么直径是2 ，其他的时候是3 我们还讨论了关于平面图不完全选色的问题若对任一定点给定七种颜色的 列表，染色时每个顶点的颜色只能从自身的颜色列表中选择且每个顶点至多有d 个邻点和它染相同的颜色，总存在图g 的一个顶点的正常着色，则图g 称为 ( k ，d ) 。一可选色的在第二章中证明了一个周长不小4 且不含5 一，昏圈的平面 图，如果它至多有4 个4 圈，那么这个图是( 2 ，2 ) 匕可选色的还证明了一个 周长不小4 且不含5 一，6 一圈的平面图，如果它含有4 匿的个数至多为5 ，那么 这个图是( 2 ，3 ) l 可选色的 关键字：最小直径，定向，周长，甲面图，不完金选色性 p r e f a c e i ti sn 9 一c o m p l e t et od e c i d ew h e t h e ra nu n d i r e c t e dg r a p ha d - m i t sa no r i e n t a t i o no fd i a m e t e r2 t h ef o l l o w i n gi s aw e l lk n o w n t h e o r e mo fr o b b i n s 1 1 ：ac o n n e c t e dg r a p hgh a sas t r o n g l yc o n n e c t e do r i e n t a t i o ni fa n do n l yi fgh a sn ob r i d g e t h e r e f o r e ，w e c o n s i d e rh e r eo n l y ( c o n n e c t e d ) g r a p h sw i t h o u tb r i d g e s f o rag r a p h g 1 e tg 7d e n o t ea no r i e n t a t i o no fgh a v i n gm i n i m u mf i n i t ed i a m e t e r d e f i n e ( n t ，凡2 ，- n 女) = d i a r a ( k ( n l ，n 2 ，- 几k ) ) b o e s c ha n d t i n d e l lf 2 1p r o v e dt h a t ，( n ，礼) = 3f o rn 2 p l e s n i k 3 is h o w e d t h a ti fn l ，扎2 2 ，t h e n ，( n l ，n 2 ) 4 s o l t e s 3 d e t e r m i n e dt h ee x a c t v a l u eo f ，( 佗1 ，几2 ) f b ra l ln l ，n 2 i f 凡l2n 2 2 ，t h e n ，( n 1 ，n 2 ) = 3 f o rn i ( f 0 2 ) ，a n do t h e r w i s e 1 ，n 2 ) = 出as h o r tp r o o fo ft h i s r e s u l tb yu s i n gt h ew e l lk n o w nt h e o r e mo fs p e r n e ri sg i v e ni n 4 j f i n a l l y ，p l e s n i k 5 la n dg u t i n 6 jp r o v e dt h a ti f 七3 ，t h e n2 厂( n l ，n 2 ：- n ) 3f o ra l in ；( 。= l ，2 ：，庇) a n d ，( n ，n ，n ) = 2 ， u n l e s s 惫= 4a n dn = l ，i nw h i c he s n ef ( 1 ，l ，1 ，1 ) = 3 i nc h a p t e r 1 w ew i l ld i s c u s st h em i n i m a ld i a m e t e ri no r i e n t a d o no ft h es p e c i a l ，n ，_ - - - - ，、_ _ 。 c o m p l e r , em u l t i p a r t i t eg r a p h sk ( 。l ；l ，一：1 ，佗) a g r a p hg i sc a l l e df 七，d 卜c h o o s a b l ei ff 。i 。e v e r yi i s ta s s i g n m e n t s a d s f y i n gl l ( u ) l = 七f o ra l lu v ( a ) t h e r ei sa l ll c o l o r i n go f g s u c h c l 】a ce a c hv e r t e xo fgh a sa tl i l o s l ：dn e i g h b o r sc o l o r e dw i c ht h e s a n l e l o ra si t s e l f s k r e k o v s k i 9 1a n de a t o na n dh u l l 1 0 p r o v e dt h a i e v e l 、p l a n a rg r a p hi s ( 3 ! ) + 一c h o o s a b l ea n de 、e r yo u t e r p l a n a rg r a p h i sf 2 ，2 ) + c h o o s a b l e s k r e k o v s k i 11 p r o v e dt h a te v e r yp l a n a rg r a p h w i t h o u t3 - c y c l e si s ( 3 ，1 ) + e h o o s a b l e i n 1 l i ，i tw a sp r o v e dt h a te v e r y p l a n a rg r a p hw i t h o u t4 - c i r c u i t sa n t l - c i r c u i t sf o rs o m ef 5 ，6 ，7 ) i s f 3 ，1 ) + 一c h o o s a b l e d e n o t eb yg dt h es m a l l e s tn u m b e rs u c ht h a te v e r y p l a n a ro fg i r t ha tl e a s tg di s ( 2 ，d ) + c h o o s a b l e ，i n 2 2 ，i ti ss h o w n t h a t g l 9 ，虫s7 ，乳s6a n do o d = 5f o re v e r yd 4 w ew i l ld i s c u s s d e f e c t i v ec h o o s a b i l i t yo fs o m ep l a n eg r a p hi nc h a p t e r2 c h a p t e r1 m i n i m u md i a m e t e ri n o r i e n t a t i o n so f 上f 诜v 上岛 1 1i n t r o d u c t i o n ad i r e c t e dg r a p h ( o rj u s td i g r a p h ) dc o n s i s to fan o n e m p t yf i n i t es e t v ( d ) o f e l e m e n t sc a l l e dv e r t i c e sa n daf i n i t ea ( d ) o fo r d e r e dp a i r so f d i s t i n c tv e r t i c e sc a l l e da r c s w ec a l lv ( d ) t h ev e r t e xs e ta n da ( d ) t h ea r cs e to fd w ew i l lo f t e nw r i t ed = f va ) w h i 出m e a i l 8t h a t va n daa r et h ev e r t e xs e ta n da r cs e to fd ，r e s p e c t i v e l y f o ra n a r ef u ，i u lt h ef i r s tv e r t e xui s i t st a i la n dt h es e c o n dv e r t e xui si t s h e a dw ea l s os a yt h a tt h ea r em iv ) l e a v e sua n de n t e r su t h eh e a d a n dt a i lo fa na r ca r ei t se n d v e r t i c e s ；w es a yt h a tt h ee n d v e r i c e s a r ea d j a c e n t i f ( 札，u ) i sa na r c ，w ea l s os a yt h a tud o m i n a t e s 训( o r ui sd o m i n a t e db yu 1a n dd e n o t ei tb yu ，u f 0 王d i s j o i n ss u b s e t s xa n dyo fv ( d 1 x y 。l l l e a n st h a te v e r yv e r t e xo fxd o m i n a t e s e v e r yv e r t e xo fy f o rav e r t e xi nd ，w eu s et h ef o l l o w i n gn o t a t i o n ： 上( l 一) = 2 。p 7 一u ：u u a ) ：二v 一( u ) = 矿一u ：l u u ) t h e s e t s + ( u ) v 一( u ) a n dn ( v ) = + ( u ) u v 一( u ) a r ec a l l e dt h eo u t n e i g h b o r h o o d i n n e i g h b o r h o o da n dn e i g h b o r h o o do fu 讹c a l l t h e v e r t i c e si n v + ( ，) - v - ( u ) a n d ( l ，) d i eo t l g n e i g h b o r s ，i n n e i g h b o r s a n dn e i g h b o r so f d e n o t en + h = ) up n = n - ( 。1u u ) a n dn v ：( u ) u ) i nad i g r a p hd = ( ka ) ，i fza n dya r ev e r t i c e so fd ，t h e nt h e d i s t a n c e ? r o m 。t oyi nd ，d e n o t e dd i s t ( z ，可) ( o rj u s td ( z ，y ) ) ，i s t h em i n i m u ml e n g t ho fa 仕，可) 一w a l k ，i fyi sr e a c h a b l ef r o mz ，a n d o t h e r w i s ed i s t ( x ，y ) = 。( o rj u s td ( 。，可) ) i tf o l l o w st h a td i s t ( x ，z ) = 0f o re v e r yzev t h ed i s t a n c ef r o mas e tx t oas e tyo fv e r t i c e s i ndi sd i s t ( x ，y ) = m a x d i s t ( x ，y ) ：xex ，y y ) t h ed i a m e t e r o fdi sd i a m ( d ) = d i s t ( vv ) c l e a r l y ，dh a sf i n i t e , d i a m e t e ri fa n d o n l yi f di ss t r o n g l e tg = ( v ( g ) ，e ( g ) ) ，s u p p o s et h a tv 7i sa 。n o n e m p t ys u b s e to f v t h es u b g r a p ho fgw h o s ev e r t e xs e ti sv 7a n dw h o s ee d g es e t i st h es e to ft h o s ee d g e so fgt h a th a v eb o t he n d si nv 7c a l l e dt h e s u b g r a p ho fg i n d u c e db y a n di sd e n o t e db ya i r ， t h ei n d u c e d s u b g r a p hc v v 7 】i sd e n o t e db yg v 7 ga n d 日a r ed i s j o i n ti ft h e y h a v en ov e r t e xi nc o m m o n ，a n de d g e - d i s j o i n ti ft h e yh a v en oe d g ei n c o m m o n t h eu n i o nguho fga n dh i st h eg r a p hw i t hv e r t e xs e t v ( c ) u v ( h ) a n de d g es e te ( g ) u e ( 日) i f ga n d 日a r ed i s j o i n t ，w e s o m e t i m e sd e n o t et h e i ru n i o nb yg + 日t h ej o i n tg vho fd i s j o i n t g r a p h sga n d 日i st h eg r a p ho b t a i n e df r o mg + h b yj o i n i n ge a c h v e r t e xo fgt o e a c hv e r t e xo fh km k ni st h eg r a p ho b t a i n e df r o m k m + 1 ib y3 0 i n i n ge a c hv e r t e xo fk m t oe a c hv e r t e xo fk n 1 2m a i nr e s u l t sa n dk n o w nl e m m a s t h ef o l l o w i n gi sa v e l lk n o w nt h e o r e mo fr o b b i n s1l ：ac o n n e c t e d g r a p hgh a sas t r o n g l yc o n n e c t e do r i e n t a t i o ni fa n do n l yi fg h a si i 0 b r i d g e t h e r e f o r e jw ec o n s i d e rh e r eo n l y ( c o n n e c t e d ) g r a p h sw i t h o u t b r i d g e s f o rag r a p h g 1 e tg 7d e n o t ea no r i e n t a t i o no fgh a v i n gm i n i i l l t l mf i n i t e ( 1 i a m e t e rd e f i n e ，( n l ? 1 2 ，7 l i , ) = d i a m ( n 7 ( n 1 n 2 ，。3 h ) ) b o e s c ha n dt i n d e l lf 2 1p r o v e d t l l a tf ( ，! ，7 ) = 3f o rn 2 p l e s n i k 3 j s h o w e dc h a ti fn l ，n 2 2 7t h e n ，( 扎i ，7 2 2 ) 4 s o l t e sf 3 d e t e r m i n e dt h ee x a c tv a l u eo ff ( n l ，n 2 ) f o ra l ln l ：n 2 ：i fn l 诧2 2 ， t h e nf ( n l ，佗2 ) = 3f o rn l ( n 2 2 1 ) ，a n do t h e r w i s e ，( n l ，7 2 2 ) = 4 as h o r tp r o o fo ft h i s r e s u i tb yu s i n gt h ew e l lk n o w nt h e o r e mo f s p e r n e ri sg i v e ni n ( 4 i f i n a l l y , g u t i n 6 】p r o v e dt h a ti fk 芝3 ，t h e n f ( n l ，n 2 ，n ) 3f o ra l l 扎t ( i = 1 ，2 ，一，惫) a n df ( 7 2 ，n ，n ) = 2u n l e s s 七= 4a n dn = 1 l e m m a1 。1 ( p l e s n i k 5 ja n dg u t i nf 6 3 ) t f k 3 、t h e n2 曼f ( n l 。n 2 ： 他 ) 3 ；，( n ，n ，一，凡) = 2 ，u n l e s s 七= 4a n dn = 1 ，i nw h i c h e a s ef ( 1 ，1 1 ，1 ) = 3 n _ _ _ _ _ _ 。_ _ ，、_ - - 。_ 。一 s i n c e = 彤( 。l ，l ，一，f ) ( n 3 ) ，i tc a nb eo r i e n t a t e di n t o ad i g r a p hw i t hd i a m e t e r2e x c e p tw h e nn = 4 w h e nn = 4 t h e r a i n d i a mo fk i s3 n o t et h a ti nk l md i s t i n c tv e r t i c e sh a v ed i f f e r e n t o u t n e i g h b o r h o o d s l e m m a1 。2 s p e r n e r 嘲) t h em a x i m a ln u m b e ro f p a i r w f s ec o n t a i n m e n t k e es u b s e t s 。绍a nm - s e ti s ( 翟f ) d e f i n e 日( m ? 礼) = v a n dl e t 矿( h ( m ，n ) ) = x u ys u c h t h a th ( m ，n ) x = a n d 日( m ，n ) ( y 】= 瓦d e f i n e ( m ，n ) 一 d i a m ( h 7 ( m ，n ) ) i nt h i sc h a p t e r ，hd e n o t e r 2 r ( 7 7 1 ，n ) ：xa e n o t e sa nm s e t z i 2 c 2 z ，。) ，yd e n o t e sa nn s e t y i ，y 2 ) ，fi st h ef a m i l y o fa l ls u b s e t so fs i z el 号ji nxa n d 罗i st h ef a m i l yo fa l ls u b s e t so f s i z e 等1i nx 。i np a r t i c u l a r ，w h e nmi se v e n ：，= 尸 f o l l o w i n ga r eo t l rm a i nr e s u l t s ： t h e o r e m1 1f o rm = 2 p 4 - 1 p 1 矗( m ，札) = 2 t g ，z e t z e l ；e t n ( 等r n j 一玎za ? l , d ( 1 7 2 甩) = 3 枷g 扎e ? 肥r 尼( f 军f ) t h e o r e m1 2 ( 1 ) f o rm = 4 p + 2 p 0 ，矿2 ( 置) 一等，t , h e n h i m ，n ) = ! ：o t h e r w i s e7 2 ( 阮n ) = 3 、( 2 ) f o rm = 4 p p 1 矿 ，z ( 置) 一等一l 、t h e n ( h 1 ，2 ) = 2 ：o t h e ? w i s eh ( t nn ) = 3 1 3t h ep r o o fo ft h em a i nr e s u l t s c o r o l l a r y1 1 巧m 2 ，1 7 , 1 ，t h e n2 ( m ，礼) 3 m p r o o f n o t e 地a th ( m ，n ) ：( f r ? i ) ，b yl e m m a1 1 ，s ow e h a v e t h a t2 ( m ，凡) 3 口 l e m m a1 3 可n l 几2 ，t h e n ( r n ，n 1 ) ( m ，r t 2 ) p r o o f 日f m ，凡1 ) = v 蕊i s as u b g r a p ho f h ( m ，n 2 ) = k mv 匿 s of r o ma n yo r i e n t a t i o nh + ( m ，? 2 2 ) o f 日( m ，n 2 ) ，w ec a no b t a i na no r i e n t a t i o n 日+ ( m ，n 1 ) o f 可m ，n 1 ) i ti sd e a r t h a td i m a ( h + ( m ，n 2 ) ) d i a m ( h + ( m ，7 2 1 ) ) t h e r e f o r eh ( m ，m ) h ( m ，n 2 ) 口 l e m m a1 4w eh a v e 一jh ( 2 ，1 ) = 2a n dh ( 2 ，n ) = 3 ，0 r n 2 ， 倒h ( 3 ，n ) = 3 ，0 r n 1 p r o o f ( 1 ) 1o b v i o u s l yh ( 2 ，1 ) = 甄，s ow eh a v et h a th ( 2 ，1 ) = 2 d ( 2 ，2 ) i sag r a p h a sf i g u r e1 1 ( a ) a n dl e th ，( 2 ，2 ) b et h eo r i e n t a t i o n o f 日( 2 ，2 ) h a v i n gm i n i m u m f i n i t ed i a m e t e r s u p p o s et h a th ( 2 ，2 ) = 2 s i n c ee a c h 玑( i = l ，2 ) i sa d j a c e n tt ot w ov e r t i c e si n 日，( 2 ，2 ) ，o n eo f w h i c hi s o u t n e i g h b o ra n dt h eo t h e ri si n n e i g h b o ro fy i w 1 o g w ea s s u l n et h a tz l11 ，1a n dy 1 x 2 w ec o n s i d e rt h ev e r t e xy 2 c a s e1 ：i f z l * 驰a n d 抛一r ! a 8f i g u r e1 1 ( b ) ，t h e n 矗( l ，比) 2 t h i sc a s ei si m p o s s i b l e ，c a s e2 ：i f 娩一x ia n dx , 2 一9 2a sf i g u r e 1 1 ( c ) t h e nd l ，y 2 ) = f ( 驰玑) = d ( x 1 z 2 ) = d ( 上2 ，z 1 ) = 2a n d d ( 上l ，y 1 ) = d ( y t ，z 2 ) = d ( z 2 ：y 2 ) = d ( y 2 z 1 ) = 1 n om a t t e rh o w w eo r i e n t a t et h ee d g ex 1 2 8 2 ，d ( zl ，y , 2 ) o r 矗( z ! ，1 ) m u s tb e3 i ti s c o n t r a r yc o1 w p o t h e s i s s ou eg e tc j l a ch ( 2 ，2 ) = 3 b yc o r o l l a r y1 1 a n dl e m u l a1 3 w el l a v ec l l a th ( 2 t t l = 3f o rn 2 冈厌冈 9 l驰y l驰可l可2 f i g u r e1 1 ( a )f i g u r e1l ( b )f i g u r e1 1 ( c ) ( 2 ) s i n c eh ( 3 ，1 ) = ( 1 ，1 ，1 ，1 ) = 3 ：b yc o r o l l a r y1 1a n dl e m m a l3 ，w eh a v et h a th ( 3 ，n ) = 3f o rn 1 口 i ti ss m c i e n tf o ro r i e n t a t i o nt od e f i n et h eo u t n e i g h b o r si nx n o t et h a ti nt h i sc h a p t e r 暇( u ) f o r 日r e f e r st ot h es e to fo u t n e i g h b o r si nx t h ev e r t e xw h i c hi sa d j a c e n tt oyf o ra n y y m u s tb ei nx ，s ow eh a v et h a tn 十( 可) = 峨( ) l e m m a1 5r f 危( m ，n ) = 2 ，t h e n n jn 未( y i ) gn 未( y j ) w h e r e1 i j n j 俐峨( 可) 砻暇ma n d 暇( 可) 霪暇( z ) w h e r ez xa n dy y p r o o f ( 1 ) s u p p o s et h a t 支( 玑) 暇( 珊) ( j u s tn + ( 玑) n + ( 协) ) f o r1 i j 忍s i n c e ( m ，n ) = 2 ，w eh a v ed ( 纨，盼) 兰2 b e c a u s e 虮a n dy ia r en o ta d j a c e n t ，t h e r ei sav e r t e x 山s u c ht h a t 玑 wa n d w y j b u ta n yo u t n e i g h b o ro fy i i sa no u t n e i g h b o ro f 协，w i t ha c e n t r a d i c t i o n ( 2 ) a s s u m e t h a t 嗽( 可) 峨o r 暇( 钞) 暇( z ) w h e r e z x a n dy y i fa 吱( 可) 三 厂上 z w h e r ex xa n d 可y ，t h e ny 一。 s i n c ea ( m ，n ) = 2 ，w eh a v ed ( x ，y ) s2 n o t et h a tzi sd o m i n a t e db y ，s ot h e r ei sav e r t e xw xs u c ht h a tz _ 5 ua n d ”y t h eo u t n e i g h b o r so f 互i nx a r ea l lo u t n e i g h b o r so f0 ，w i t hac o n t r a d i c t i o n i f 丰( ) 丰( z ) w h e r ez xa n dy y ，t h e nt h eo u t n e i g h b o r s o f 可a r et h eo u t n e i g h b o r so f 工t h u sw eg e tt h a td ( y z ) 2 ，w i t ha c o i l l口adiction t h ep r o o fo ft h e o r e m1 1 ( 羔，) 一阮l e tp = z z i 牡 1 1 1 0 ( 1 u l e2 1 ( + 1 1g i 、e8 ni n j e c t i o no - a s s u m et h a t 七= l 筹i fn p ，。) 1 1 i 2 k + 1 ( u pt o y 一厂一p 0 1 i e n t a t eh ( m j ? ) w i t h 嘉( g ) = 矿( 可) f o ry ya n d 雌( z i ) = 。t + l ，x i + 2 。+ 2 3 i + k f o 。 1 i 2 k + 1 f o ra n yu ，u y ( 日) ，蔓( u ) 譬蔓扣) ，t h e ne i t h e r u d o m i n a t e s o rt h e r ei sav e r t e x 叫xs u c ht h a tu _ w a n d 埘 ， t h u sw eh a v et h a td ( ，u ) 2 t h e r e f o r e 九( m ，n ) 22 s u p p o s et h a th ( m ，礼) = 2w h e n 礼( i 霉1 ) i f ( m ：n ) 22 ， b vl e m m a1 5 ，t h e nn + ( 玑) 茌n + ( 协) w h e r el i j n ，a n d + ( 可) 望n + i x a n dn + ( ) 譬n + ( z ) w h e r ez x a n dy y c a s e1 w h i l e 佗 ( 1 翟f ) ，b yl e m m a1 2 ，i t i s i m p o s s i b l et h a t + ( 玑) 譬n + ( y j ) w h e n1 i j n s oh ( m ，n ) 2 3 c a s e2 w h i l en = ( 1 譬1 ) ，w eh a v et h a te i t h e rn + ( ) ff o r a l l y yo r + f ) f f o ra l ly y ，t h e r em u s t b eav e r t e x u xw i t hj + ( u ) i l 罟ja n dav e r t e xuw i t hl + ( u ) f l 予j - w h e nf 、，+ ( y ) i v y ) = f ，t h e r ee x i s t sav e r t e xy y s u c ht n a t 峨( 可) 十( u ) ，w i t hac o n t r a d i c t i o n w h e n ( + ( y ) l y y ) ；尸， t h e r e d s t sav e r t e xy ys u c ht h a t 妄( 可) 2 嗽f 】，w h i c hi s a c o n t r a d i c t i o n s o ( m ，n ) = 3 口 l e m m a1 6n jf o rn = 卸+ 2 w h e r e p l ，谚他( 霉) 一号，肮e 几 h ( m , n ) ：2 例f o rn = 4 p w h e f ep l ，矿几( 攀) 一号一1 ，地e 凡 h ( m ，n ) = 2 p r o o f ( 1 ) l e tk = 等= 2 p + l ，s u p p o s e 几= ( 霉) 一罟l e tx 2 s 。 z 2 s + l ，z 2 川，一，：z 2 s + k - 1 ( u pt om o d u l e2 k ) a n dz 2 州一+ ( 阮) u f z 。 f o r1 s 七l e tp = ( z 2 s ，x 2 州，2 ：2 s + 一l ) ，1 s 七 ； t h e n p ：( ：1 一等g i v ea ni n j e c t i o n 盯f r o my t o 芦一p ，t h e n o r l e n t a t eh ( a n ) w i t h + ( 1 ，) = 盯( 可) i tr e m a i n st oc h e c kt h a tt h e d i a m e t e ri s2 c a s elf o ra n ) ru 。v ( h ) w i t h 联( 删= i 联( u ) l2 七s i n c e 士( m ) - v 丰( u ) e i t h e r “d o m i n a t e su o rd a e r ei sa nv e r t e x 一y s l l c l lt 1 1 a cu 。l ua n dl u l s ow eo b t , a i nd ( u 。) 2 c a s e2f c ) rj ：xw i t h1 - 5 l2 - ) l = 七一1a n d ! ，y 、i f ( 12 手( z ) ，t h e nt h e r ei sav e r t e x 叫肖s u c ht h a t 训i so u t n e i g h b o ro f z b u n n o to f ；t h e r ei sa l s oav e r t e xt xs u c ht h a tti so u t n e i g h b o r o f 可b u tn o tz t h u sw eo b t a i nt h a td ( z ，y ) 2a n dd w ，x ) 2 i fn ；w ) 3 暇( z ) ，n o t et h a t 孵4 - ( 可) 嗽吼t h e nzd