（应用数学专业论文）大点数为6的色指数临界图的研究.pdf

信息工程大学硕士学位论文 摘要 图g 的边着色是对g 的边进行着色，图g 的正常边着色是使得g 中没有相邻的边染 相同颜色的边着色。图g 的正常边着色中所用颜色的最少数目称为图g 的色指数。若对 图g 进行正常边着色，g 中的任意一个大点所关联的( g ) 条边需要( g ) 种颜色，因而图 g 的色指数至少为( g ) 1 9 “年，z h 培证明得到了重要结论：对于任何一个简单图g ，它的色指数为“g ) 或 者( g ) + 1 这个定理的提出，把简单图分成了两类。给定简单图g ，若g 的色指数为( g ) ， 则称g 是1 一类的；若g 的色指数为( g ) + l ，则称g 是2 一类的。在此基础上，v i z i n g 提出 了色指数临界图的概念。如果g 是连通的，2 类的，并且任意减去g 的一条边p 得到的 子图g 叩的色指数小于图g 的色指数，则称g 是色指数临界的。色指数临界图是2 类图 中边数最少的。 a gc h e t 、 ，y n d 和a j w h i l t o n 证明得到了大点数为3 的简单图是2 一类的充分必要条 件，并证明了不存在大点数为4 的偶阶色指数i 临界图，进一步得到了大点数为4 的奇阶色 指数临界图的次数序列及其边数。hp y 却和z i x i as o n g 进一步讨论得到了不存在大点 数为5 的偶阶色指数临界图。之后，z i x i as o n 2 证明得到了大点数为5 的奇阶色指数i 临 界图的边数以及次数序列的所有情形。 本文研究了大点数为6 的色指数临界图的性质。第一部分介绍了图的基本概念及色指 数临界图的一些结论。在第二部分中，首先证明了若大点数为6 的偶阶色指数临界图存在， 则它有完美匹配，继而证明得到了大点数为6 的偶阶色指数临界图不存在。在第三部分讨 论了大点数为6 的奇阶色指数临界图的简单性质及构造。 关键词：边着色，色指数，临界图，大点 第页 信息工程大学硕士学位论文 a b s t r a c t e d g ec o l o r i n g o f a g 豫p h g i s t oc o l o r t l l ee d g e so f g a p r o p e re d g e c o l o 血g o f gs a t i s f i e s n ot w oa d j a c e me d g e so fgr e c e i v e 也e m e 1 0 r s t h ec l l r o m a _ c j ci n d e xi s t 1 1 em i i l i m 啪 n u m b e ro fa l lp o s s i b l ep r o p c re d g ec o l o r i n g so fg s i n c eav e n e xl l a v i n gm a ) ( i m u md e g r e ei s i n c i d e mw i m e d g e s 州c hr e q 毗c o l o r s ，t l l ec h r o m a t i ci n d e xo fgi sm o r et h a l lt h e m a x i m u m d e g r e eo fg n l e 妯d a r n e i 】_ t a lt h e o r e mo fe 如ec o l 耐n g ，m a d eb y z i n gi i l1 9 6 4 ，c l a i m st h a t 畦l e c h r o m a t i ci n d e xo f a r b i t 哪rs h n p l e 卿hgi se q l l a lt o g ) o r ( g ) + 1 i f 也ec h r o m a t i ci n d e x o f g i s e q u a l t o ( g ) ，t h e n g i ss a i d t ob co f c l a s sl ，o t h c n v i s e g i ss a i d t ob eo f c l a s s2 1 1 1 e n 洳gi n 仃o d u c e dt h et e n n i n o l o g yo fc r i t i c a l 群印h s ，t og n l d yt h ec l a s s i f i c a t i o no f c l a s sl 口a p h s a n dc l 鹊s2 簪a p h s ag r a p h g i ss a i d t ob cc h r o m a t i c i n d c xc r i t i c a l i f g i sc o n n e c t e d ，o f c l a s s2 ， a i l dt h ec h r o m 撕c 砌e xo f g - el e s st l l a nt 1 1 a to f g s ，f o ra 1 1 ye d g epo f g t h er e s e a r c h 衄c h r o m a t i ci n d e xc r i t i c a lf a p hi si m p o r t a n tt oe 丑g ec o l o r i n g t h es i 乃e so f c h r o m 撕ci n d e x 嘶t i c a l 伊a p h sa r e1 1 l el e 硒to fc l a s s2 黟a p h s s of 犯a gc h e t w y n da n da j w h i l t o ns h o w e dt l l en e c e s s a r ya i l ds u 筒c i e n tc o n d i t i o i l so fas i m p l e 掣a p hw i t ht i l r e em a j o r v e n i c e si so fc l a s s2 t b e nt h e yp r o v e dt h a ta n yc h r o m a t i ci n d e xc r i t i c a lg r 印ho fe v e no r d e r 晰t hf o i l rm a j o rv e n i c e sd o e sn o te x i s t ，a i l dm es i z eo fc h r o m a t i ci n d e x 掣a p ho fo d do r d e r 埘m f o l | rm a j o rv e n i c e si sp r e s e n t e d h p y a p 甜l dz i x i as o n ga l s op r o v e da n yc h r o m a t i ci n d e x c 确c a lg r a p ho f e v e i lo r d e lw i t h6 v em a j o rv 硎c e sd o e sn o t “i s t 1 1 1 e nt 1 1 es i z eo f c l l r o m a t i c i n d e x 卿ho f o d do r d e rw i t hf i v em 勾o rv e r t i c e si sf i x e d b yz i - x i as o n g i nm i sp a p w ed i s c l l s sm ec h r o m a t i ci n d e x 掣a p h s 诵t l ls 奴m a j o rv e n i c e s 1 1 1s e c t i o nl ， w ei l l 仃0 d u c es o m ec o n c e p t sa n dt h c o r e m so fc h r o m a t i ci n d e xc r m c a l 鲫p h s i i ls e c t i o n2 ，f i r s t ， w es h o wm a ti fc l l l o m a t i ci l l d e xc r i d c a l 孕_ a p hgo fe v e no r d e rw “hs i xm a j o fv e n i c e se x i s t s ， t h e i lg l 勰ap e 疵c tm a t c h i n g n e nw ep r o v et h a tc b 3 m a t i ci n d e xc 正t i c a lg r a p ho f “e no r d 盯 、玑ms i ) 【m a j o rv e r t i c e sd o e sn o te x i s t i i ls e c t i o n3 ，w er e s e a r c ho nt b ec h r o m a t i ci n d e xc r i t i c a l f 印ho f o d do r d e rw i 也s i xm 萄o iv e n i c e s ，a 1 1 dg e ts o m es i m p l ep r o p e n i e sa b o u t t h e m k e yw o r d s ：e d g ec o l o 咖舀c i 们m a t i ci n d e x ，t i c a lg r a p h ，m 勾o rv e r t e x 第1 i l 页 原创性声明 本人声明所旋趸的学位论文是本人在导师指导p 进行的研冤工作及取得的研冗成果。 尽我所知，除了文中特鄹加以标注和致谢的地方外，论文中不包含其他人已经发表和撰写 过的研究成果，也不包含为获得信息工程大学或其他教育机构的学位或证书而使用过的材 料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 意。 学位论文题目：叁星l 氐翌丛垒鲞& 盔蛰迄姚盔整 学位论文作者签名： 卷塑日期：去司年干月占日 作者指导教师签名：二型豇塾口公么二一日期：如刁年年月心同 学位论文版权使用授权书 本人完全了解信息工程大学有关保留、使用学位论文的规定。本人授权信息工程大学 可以保留并向国家有关部门或机构送交论文的复印件和电子文档，允许论文被查阅和借 阅；可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目：太苎墨t 壹丛生基隘煎! 盛盈匦盈逢 学位论文作者签名：塞 貂日期：加矿年年月心日 作者指导教师签名：j 聋兰 呈堂么二一一日期：为器年月d 日 信息工程大学硕士学位论文 第一章绪论 图论是一个新兴的数学分支，近半个世纪发展十分迅速，在许多领域都有广泛的应用。 图的着色问题是图论的重要分支之一，现实生活中的许多问题，如排课问题、存储问题、 电路安排问题、交通状态等，都与图的着色理论密切相关。所谓图的着色是指对图的点、 边或其他对象按照一定的规则进行分类，对象不同或者规则不同，便有不同的着色，如点 着色、边着色、点边全着色、点边面全着色以及其他一些特定的着色。其中，图的边着色 问题是图着色理论中一个基础问题。在图的边着色理论的研究中，著名的v i z i n g 定理的 提出，把简单图分成了两类。在此基础上，v i 殖l g 又提出了色指数临界图的概念，它对图 的关于色指数的分类问题有重要意义。本文研究了大点数为6 的色指数临界图的性质。 1 1 图论的基本术语 本文考虑的图都是有限的、无向的、非平凡的简单图。未定义的术语和记号可参见文 献【l ，2 】。 给定一个图g ，h g ) 、日g ) 、( g ) 和文g ) 分别表示图g 的点集、边集、最大次数和 最小次数。图g 的阶是g 所含点的个数，记为| h g ) f 或简记为i g f ；图g 的边数用e ( g ) 表示。只有一个点的图称为平凡图，其他所有的图都称为非平凡图。 如果图g 的两个点“和v 有边连接，则称材和v 相邻，并称v ( 或“) 是“( 或v ) 的邻点。 点“的所有邻点的集合叫做“的邻域，记作g ( “) 在不产生混淆的情况下， h “) 可简记 为( g ) 因为g 是简单图，所以点“的次数为( ) l ，简记为顶“) 图g 中各点次数最大 者( 最小者) 称为g 的最大次数( 最小次数) ，记为( g ) ( 氓g ) ) 如果一个图的每一个点都具有 相同的次数，则称这个图是正则的。每个点的次数均为女的正则图，称为缸正则图。如果 g 的阶为仃，且每个点的次数都是o ( 或n 一1 ) ，则称g 为空图( 或完全图) ，记为仉( 或) 对 于边p = w 以g ) ，称点”和v 是e 的端点，称“，v 分别与边p 关联，称点“和v 是相邻的。 若图g 的两条边p 和，有一个公共的端点，则称边p 与厂相邻。 对h g ) 中有两个不交子集彳，占，用口，召】g 表示一个端点在4 中，另一个端点在曰中 的所有边的集合，令所g 口，明= 【彳，明g i 也可以用p 利，占) 表示图g 中点集爿和b 的连 边数，其中，彳和b 的交集不一定非空或者爿和占可以使同一个集合。用s 表示g 中次 数为i 的点的集合，令m 尸l s 】，则g 的次数序列可表示为l 码2 呜七如果埘，_ o ，因子 0 在次数序列中省略。 二 图g 的点集合坎g ) 分成子集h ，圪( h u 乃= h 回，h n 圪= a ) 的分划( 巧，圪) ，称为g 的二分划。设图日是一个以h g ) 为点集的图，若日中的两个点是相邻的当且仅当它们在 g 中不相邻，则称日为g 的补图，记作日= g 或日= g 如果坎日廷坎g ) ，e ( 功s 以g ) ，则称图日是图g 的子图，记作丑塞g 假设矿7 是矿的 第1 页 信息工程大学硕士学位论文 一个非空子集，以矿为点集，以两端点均在矿中的边的全体为边集所组成的子图，称为 g 的由矿导出的子图，记为g 【y 】g 【】称为g 的导出子图。导出子图g 【矿】记为 g 一，它是从g 中删除中的点以及与这些点相关联的边所得到的予图。假设e 是e 的一个非空子集，以f 为边集，以f 中边的端点的全体为点集所组成的子图称为g 的由 f 导出的子图，记为( e ) 称为g 的边导出子图。 设g l 和g 2 是g 的子图，若g l 和g 2 没有公共点，则称它们是不相交的；若g l 和 g 2 没有公共边，则称它们是边不重的。g i 和g 2 的并图是指g 的一个子图，其点集为 坎g i ) u h g 2 ) ，其边集为以g 1 ) u 耳g 2 ) ，记为g l u g 2 设g 和日是两个图，如果存在一个一一映射磅坎g ) _ 以劢，使得“v 耳g ) 当且仅当 吠“) 故v ) 以，则称图g 和日同构，记作g 兰h 图g 的一条途径是指一个有限非空序列蹄，- v 妒i v l 晚v 2 p 以，它的项交替地为点和边， 使得对l f r ，毋的端点是h i 和h 称矿是从到v ，的一条途径，或一条( v 0 ，一途径。 点和h 分别称为形的起点和终点，称为形的长。若途径形的边口l ，p 2 ，即互不相 同，则称矽为链。若v 0 h ，则称其为开链；若v 0 ，v ，互不相同，则称它为路。长度为 盯的路记为以如果除去v o = v ，外，这条链的其余点皆不相同，此时称它为圈。长度为珂 的圈称为胛圈，记为g 根据 的奇偶性，称一个n 圈为奇圈或偶圈。3 圈常称为三角 形，4 圈常称为四边形。如果图g 的一条路p 包含了g 的所有点，那么路j p 就称为g 的 h 砌i l t o n 路。含有图g 的所有点的圈称为g 的h 锄i l t o n 圈。含有h 砌i l t o n 圈的图称为 h 锄i l t o n 图。 设m 是目g ) 的一个子集，若肘中的任意两条边都不相邻，则称m 为g 的独立边集， 也叫匹配。包含图g 的所有顶点的一个匹配称为g 的1 因子，也称之为图g 的一个完美 匹配。 任意两个点都有一条路连接的图称为连通图。若图g 中两个点”和v 是连通的，我 们把g 中最短的( “，v ) 路的长记为点”和v 之间的距离，记作碳“，着y 的子集矿使得 g 一不连通或是平凡图，则称矿为g 的点割。缸点割是指包含七个元素的点割。若图g 是连通图，则称g ) = 埘拥 if 是g 的点割 为g 的连通度。当图g 为平凡图或不连通 图时，“g 译o 着“g 1 七，则称g 为矗连通的。 最后介绍一个在讨论过程中用到的一个特殊图。我们称图g 为p e t e r s e n 图，若顶点 集h g ) ： v o ，v l ，v 2 ，v 3 ，v 4 ，珈，蝴，地，蚴，m ，边集以g ) = ( ”，“一1 ) ，m ，v 州) ，( v 。v 舵) l 枷， 4 ，其中角标模5 得到。 1 2 临界图 图g 的矗边着色是一个映射万：取g ) 一 l ，2 ，妨，使得g 的相邻边没有相同的象。 本文简称七边着色为珏着色。图g 的色指数x ( g ) = m i n ig 有一个缸着色) 。1 9 6 4 年， v i z i n g 证明了一个重要结论3 】：对于任何简单图g ，有) c ( g ) = ( g ) 或) c ( g ) = ( g ) + 1 如果 第2 页 信息工程大学硕士学位论文 x ，( g ) = ( g ) ，则称g 是1 类的；否则称g 是2 类的。在边着色的研究中，最重要的定理 就是v i z 血g 定理，它的提出，给出了简单图的一个按色指数的分类。 如果g 是连通的2 类图，并且对g 的每一条边e 都有 c 7 ( ( 卜e ) 4 由定理1 2 ( 3 ) ，( ( “，v ) ) “，v 的每个点都是大点。因为g 恰有6 个大 点，所以一2 瞰( “，v ) ) “，v ) l 6 若( ( “) 、 y ) ) 、( ( v ) “ ) o ，设w ，是( “) ( v ) 中的大点，则w 与一1 个大点相邻。由 此得，= 6 ，硪功= 吠“) = 4 ( ( “，v ) ) 、 ，v ) 中每个点都是大点，所以g a 中至少有9 条边。于 是瓯与小点至多有6 一1 8 = 1 8 条边连接。因为g 6 与“和v 有6 条边连接，所以瓯与其它 2 n 一8 个小点至多有1 2 条边连接。因为每个点至少与两个大点相邻，所以2 n 一8 鲻于是 h 4 ，即结论( 2 ) 成立。 第6 页 信息工程大学硕士学位论文 引理2 2 设g 是2 玎阶临界图，i g j = 6 ，q 是由3 个点导出连通子图，则历g q ，q 】+ 2 证明：因为i q p 3 ，所以2 鱼( q ) 3 由引理2 1 ( 2 ) ，若p ( q i = 3 ，则 州g q ，q 】知( q ) ( + 3 ) 2 2 e ( q ) 弘+ 2 若p ( q ) = 2 ，则肌g 【q ，耍】筮( + 3 卜_ 4 弘+ 2 引理2 3 设g 是2 竹阶临界图，i g 卜6 ，q 是图g 的一个至少由5 个点导出的奇阶 的连通子图。若肌g q ，豆】，我们有 ( 1 ) 若掰g 眩互】 6 t g ) + 1 ( 2 ) 若加g q ，q 】= ，则l q l 氓g ) 证明：令6 = 文g ) 由定理1 1 ，6 = l g l 一西2 ，故擗4 由定理1 4 ，不存- 正则的 临界图，因而罡一1 即4 据一1 若q 有一点不与豆的点相邻，贝l j 酗湃i ，结论成立。 设q 的每一点都与豆的点相邻，则脚o q ，亘倒研 若q 有一点x ，使得优g 防，耍】- l ，则蚓翻i ) d 因为x 至少与两个大点相邻，所以q 中至少有一个大点v 。于是l q 【+ 删g 【v ，互】+ 1 若聊g 【v ，互】= 1 ，则吲2 丹1 ，结论成立。 若聊g 【v ，q 】2 ，则 _ l ，l g 【q ，互】iq l + m g 【v ，豆卜1 弘 因为肌g q ，耍】! i ，所以所g 【q ，耍1 = ，l q 点 下面证明若q 的每个点至少与豆的两个点相邻，则lq l = 5 设“是q 中使肼g 【豆，“】= 七最小的点，则肼g 【耍，q 】七j 剑因为脚g 【百，g 】，所以 2 敛“剑因为“在q 中有反卜七个邻接点，所以i q l 碳“) 针1 因为占_ _ 4 ，所以 所g 互，q 】纠q i 瓿舐“卜抖1 ) 戡一扛3 ) = 怂萨一3 七 ( 2 1 ) 若i g 7 ，当艺时，( 胁3 ) ( 扣1 ) s 5 1q 1 于是 第7 页 信息工程大学硕士学位论文 因为i q i ，所以 由( 2 1 ) 和( 2 - 2 ) 式， ( 抖3 ) | d 扣1 七2 + 3 扫颤七+ 3 卫丛( 蚪3 ) ，i g 2 时，( 抖3 ) “扣1 ) 3 2 ，则肌g 【q ，耍】 蚓于是 2 聊g 【g ，耍】 i q f t 一t t 3 娩， 矛盾。 现在设对q 任一点x ，都有所g b ，豆】- 2 ，则所g f q ，互】= 2 1q f ，若q 中有一点的次数大 于西则吲西结论成立。若q 中每个点的次数都是a 则占= 一1 ，蚓= 一2 于是 聊g 【垂，q 】= 2 iq i = 2 4 ， 矛盾。所有情形被考虑，故引理2 3 成立。 定理2 4 若g 是偶阶一l l 缶界图，且i 瓯i = 6 ，则g 有完美匹配。 证明：设l g - 2 n 因为不存在阶小于1 6 的偶数阶临界图，所以疗8 设墨文由定 理1 1 ，6 = i g | 一辞2 ，故刚，壁4 设v 是g 中次数为巧的点。由定理1 1 ，( v ) 中每个点至少与一万+ 1 个大点相邻。考 虑g 的由至少有1 个端点的次数是的边导出的子图g ，在g ，中计算g 的大点的次数之 和，我们有 ； ( 一占+ 1 ) j + 2 ( 2 押一6 ) 6 由这个不等式，我们能得到下面的结论。 结论l 当j = 一1 时，丑3 第8 页 信息工程大学硕士学位论文 结论2 当艿_ _ 2 时，( 4 ，l 2 ) ，5 结论3 当万= 一3 时，伊1 结论4 当萨_ 4 时，h 一1 若g 没有完美匹配，由定理1 5 ，g 存在一个点集s ，使得o ( g _ 固 研因为i g i 是偶数 所以o ( g 固= 阁( m o d2 ) ，即 o ( 町i 习+ 2 ，i 耶魏一1 由定理1 1 7 ，f f 每界图是2 连通的，所以月一1 2 闯2 用表示由g 嗒的平凡支的点构 成的集合，表示中小点的集合，& 表示中次数为占的点的集合。先证几个引理。 引理2 4 1s o ，即g _ 墨有平凡支。 。 假设g s 没有平凡支，则g s 中每一个奇支至少有3 个点。 若g _ s 中没有至少由5 个点导出的奇支。由引理2 2 ，每一个奇支q ，都有历g ( q ，嗣+ 2 所以s 中至少有1 个点的次数不小于o ( ) ( + 2 ) i 翻 + 2 ，矛盾。 若g _ 书中至多有2 个至少由5 个点导出的奇支。同理，s 中也至少有1 个点的次数 不小于( o ( g 固- 2 ) ( + 2 ) “习+ 2 ，矛盾。 因为o ( g ) 1 司+ 2 ，所以g s 至少有3 个至少由5 个点导出的奇支q 若在这些至少 由5 个点导出的奇支q 中，至多有2 个满足m g 【sq 】 ，矛盾。因而g - s 至少有3 个满足朋g 【墨q 】 的奇支q ，且 这样的奇支q 至少由5 个点导出。由引理2 3 ，吲碑1 一3 因为趁桷，所以蚓 一1 于 是一4 艿丛一3 ，吲一3 由结论3 和4 ，劲一1 于是这三个满足研g 盼翻 i 1 因为n 8 ，所以 7 情形3 1 若占= 一3 ，则 i 习( 4 一妨( 2 ，( ) i 6 + 的一4 + + 占( 2 一句一i 岛 第1 0 页 信息工程大学硕士学位论文 当女= 3 时， i 习2 2 l ( ) i _ 4 + 2 一i & f ， 矛盾 当辫时， i 习2 + 2 一i 岛p ， 矛盾。 情形3 2 若占= 6 4 ，则 2 i 跚 ( 5 七) ( 2 i ( 岛) i - 6 + 分- 4 + 尬+ j ( 2 以卜慨i 当肛3 时， 2 阍 6 i ，) i - 6 + 2 一j 蹄| 由此得i 司 ，矛盾。 当榭时， 2 旧筮眦) i + 2 + 2 扣吲 由此得i 习 ，矛盾。 综上，当一l 艿一4 时都出现矛盾，故引理2 4 4 成立。 引理2 4 5 冷7 l i 两， 由引理2 4 2 ，s 中至少有妙卜- 蚓+ 1 个大点。 ( 1 ) j 2 一2 若嗲7 i = 旧，则o ( g ? 回i 习+ 2 = 涔i + 2 ，所以g i $ 至少有两个非平凡奇支，而且s 中至少 有一个大点，于是i 习弘因为墟扔，所以所有非平凡支的点数之和至多为因为g s 至少有两个非平凡奇支，所以每个非平凡奇支至多有一3 个点。由引理2 t 3 ，若非平凡奇 支与s 至多有条边连接，则此非平凡奇支至少有阶点，矛盾。因而g s 的每个非平凡 奇支与s 至少有+ l 条边连接。于是 州g 暇s 】+ ( 酬一1 ) j + 2 ( + 1 ) 弘+ ( s 卜_ 1 ) ( _ 2 ) j + 2 ( + 1 ) = l 习( 缸2 ) + 2 “ 另一方面，因为j s 中至多有5 个大点，所以 刀口g 耻孽】5 + ( i 嗣一5 ) ( 一1 ) = ( 一2 ) j 习+ i 习+ 5 由上面两式，得i 圈趁一1 于是 i 习+ p i 4 2 丑月+ 缸2 旧， 第1 1 页 信息工程大学硕士学位论文 矛盾。 若l s ，l 嘲，则s 冲至少有两个大点，于是l 习，i + l ，即l + i 司盟+ 1 因为6 鼍 至少有一个非平凡奇支，所以 2 腔峪j + 阎+ 3 艺“， 得s n - 2 由结论2 知，艿= 一1 因为g _ $ 至少有一个非平凡奇支，所以 m g 陋，季】复+ ( 降i 一2 ) ( 一1 ) + 2 = i 吲( 一1 ) + + 3 另一方面，因为s 中至多有4 个大点，所以 聊g 【s s 】g + ( 1 q 4 ) ( 一1 ) = 阍( _ 1 ) + 4 由上面两式，得s 1 ，矛盾。 ( 2 ) 一3 6 一4 由结论3 和4 ，劫一1 若翻，由引理2 4 2 ，s 中至少有一个大点。于是i 嗣= 肛1 ， 即g s 没有非平凡奇支，与引理2 4 4 矛盾。 综上，当一1 j 4 时都出现矛盾，故引理2 4 5 成立。 下面完成定理2 4 的证明。由于一1 2 艿4 ，我们分四种情形： 情形1 盎一l 由引理2 4 1 ，g $ 有平凡支。因为盎一1 ，所以j 习一1 因为2 n 3 ，所以g s 至 多有一个支含有个点。否则，若g 齿至少有2 个支含有个点，则 2 “l + 舻1 立“1 + 阍虫胛 得立3 于是_ 2 3 ，i 司= 一l ，i = 1 所以o ( 铘) i 习+ 2 = + 1 ，并且有 2 + 3 ( 一3 ) + 峪l + 一1 1 2 珂， 得刀鲥，矛盾。 若g $ 有一个非平凡奇支q ，使得肌g 晦q 】勤，由引理2 3 ，i q l 一1 由引理2 4 5 ， g 至少有三个非平凡奇支。于是这三个非平凡奇支所含的点数至少是+ 5 因为l 习一1 ， 所以其它的支所含点的个数至多是_ 4 这表明o ( g 固s 一1 阎，矛盾。这个矛盾表明， 若q 是g 哂的一个非平凡奇支，则m g 晖q 】 因为g 至少有三个非平凡奇支，所以 ， m g 【墨f ( i s 卜1 ) ( _ l 卜3 ( + 1 ) 2 i 习( - 1 ) + 2 + 4 ， 另一方面，s 中至多有6 个大点，所以 m g 暇豆】 因为g s 至少有三 个非平凡奇支，所以 研6 瓯吾】 ( 降i - 1 ) ( - 2 ) + 3 ( + 1 ) = ( _ 1 ) i 司一阶2 + 5 ， 另一方面，s 中至多有6 个大点，所以 聊g 晖j 】如+ ( 跚一6 ) ( 一1 ) = ( 一1 ) l 嗣+ 6 由上面两式，l s l 2 一l 尼+ 3 ，矛盾。 所有情形被考虑，故当出一2 时，g 有完美匹配。 情形3 参一3 由引理2 4 1 ，g s 有平凡支。因为出一3 ，所以i 嗣一3 由结论3 和4 ，洳一1 由 引理2 4 5 ，g $ 至少有三个非平凡奇支。于是 阡一l 1 习一3 ；：h l 一3 = 棚 若g s 有一个非平凡奇支q ，使得m g 瓯q 于是 l 肌g p s j 2 ( j s 卜1 ) ( 一3 ) + 3 ( a + 1 ) = 】司( 一3 ) + 2 + 6 ， 另一方面，s 中至多有6 个大点，所以 肌g 【墨s 】6 + ( i 司6 ) ( 一1 ) = 阎( 一1 ) + 6 ， 第1 3 页 信息工程大学硕士学位论文 由上面两式，阁矛盾。故当舞一3 时，g 有完美匹配。 情形4 庐小4 与情形3 类似，我们有g 至少有三个非平凡奇支，劲一1 阍- 4 舻5 由引理 2 1 ( 2 ) ，瑟4 ，故监8 ，晓4 因为卜l ，所以疗9 子情形4 1 躅= 玢- 5 这种情形表明= n 一1 由引理2 4 1 ，g o 有平凡支，此时g 墨的平凡支中的点次数都 是a 因而s 中每个点都是某一个占次点的邻接点。设s 中有七个大点，则2 挺6 出定理 1 1 ，s 中每个点至少与5 个大点相邻，所以由s 导出的子图g 翻至少有阎( 扣1 ) 一颤扛1 ) 2 条边。于是 卅g 晦s 】s 如+ ( 1 跚硒( 一l 卜2 旧( 肛1 ) + 颤扣i 产f 嗣( - 2 斛1 ) + ， 另一方面，若g 至多有一个非平凡奇支q ，使得肌g 晦q 】，所以 m g 【墨萝】陋i ( 4 ) + 2 ( + 1 ) + 2 = i 因( 4 ) + + 8 ， 由上面两式得 ( 5 2 的l 习+ 8 一， 当扣2 时，i 习+ 4 ，z ，矛盾。 当扣3 时，1 + 阎，矛盾。 当后= 4 时，8 + 3 煳，矛盾。 当扣5 时，1 7 + 5 i 习，矛盾。 当= 6 时，2 8 + 7 阎，矛盾。 子情形4 2i 因 胆一5 若g 心有一个非平凡奇支q ，使得肌g 盼q 蛆由引理3 ，蚓_ 4 n 一5 于是 lq j + 阎2 2 ，卜9 ， 其它的支所含点的个数至多是9 因此，o ( g 回6 于是，阎4 由引理l ，巧 4 ，所 以1 鼋= 4 ，n 于是 ，玎g 吟s 】峪j ( 一4 ) + 3 ( + 1 ) i 习( 4 ) + 2 + 7 ， ( 2 - 3 ) 若中没有次数为蹦点，则 肌g 盼s 】刚( 舡3 ) + 3 ( + 1 ) i 习( - 3 ) + 2 + 6 ， 另一方面，s 中至多有6 个大点，所以 第1 4 页 信息工程大学硕士学位论文 肌g 阵雪】s i 司( 一1 ) + 6 ， 由上面两式，阎，矛盾。 若f 中有一个次数为占的点x ，由定理1 1 ， 协) 中每个点至少与5 个大点相邻。设s 中有毒个大点。则2 埏6 ，所以由s 导出的子图g 【翻至少有j ( 扣1 ) ( 女一1 ) 2 条边。于是 肌g 晖雪】s 如+ ( i 翻啕( 一1 卜2 巧( 拓1 ) + 以扣l 产阍( h 1 ) + 萨一2 ( 肛1 ) 与( 2 - 3 ) 式比较，我们有 3 l 习2 6 ( 一1 ) + 2 + 7 一旷， 因为万 4 ，艿= - 4 ，所以8 因此，当2 艇6 时，i 司 ，矛盾。 综上，当出_ 4 时，g 有完美匹配。定理2 4 成立。 2 2 不存在大点数为6 的偶阶临界图 定理2 5 不存在大点数为6 的偶阶- j 临界图。 证明：假设存在恰有6 个大点的2