（运筹学与控制论专业论文）平面图的边染色.pdf

摘要 平面图的边染色 摘要 用g = ( k 日表示一个顶点集为y ，边集为e 的有限、简单无向 图，f l ，2 ，七 - 表示k 个颜色的集合g 的一个正常k 一边染色是一个 映射多：e ， 1 ，2 ，缸 使得相邻的边接受不同的色如果g 有一 个正常k 边染色，则称g 是k 一边可染的g 的边色数x 7 ( g ) 是使得g 是正 常k 一边可染的最小的非负整数 图g 的一5 - 边色列表是一4 - 颜色集合簇厶它指定g 的每条边e 一 个颜色集合l ( e ) 若g 有一个正常的边染色q o ，使得对每一条边e e ， q o ( e ) l ( e ) ，则称g 为l 边可染的若对每一个满足i l ( e ) l = 是， e e 的厶g 都是l 一边可染的，则称g 是k 一边可选择的g 的边列表色 数，或边选择数彤( g ) 是使得g 是知一边可选择的最小的非负整数岛 关于图的边染色问题，v i z i n g 在1 9 6 4 年证明了下述著名定理： h ( a ) x 7 ( g ) z x ( c ) + 1 ，其中，( g ) 为g 的最大度由此定理可 引出简单图的分类问题称x 7 ( g ) = a ( g ) 的简单图g 为第一类的，否 则，称为第二类的 本文在前人的工作基础上继续研究平面图的分类问题，证明了： ( 1 ) 最大度为6 且不含有7 一圈的平面图是第一类的 佗) 最大度为5 且不含禾圈或不含5 圈与相邻三角形的平面图是 第一类的 ( 3 ) 最大度为4 且不含4 到1 2 圈的平面图是第一类的 此外，研究平面图的边选择性问题，本文证明了下述结果： h ) 若g 是最大度不为5 署t 6 且不含相邻三角形的平面图，则 x ；( g ) a ( g ) + 1 关键词：平面图，边色数，边选择数，最大度 a b s t r a c t e d g ec o l o r i n go fp l a n a r g r a p h s a b s t r a c t l e tg = ( v e ) b eaf i n i t e ，s i m p l ea n du n d i r e c t e dg r a p hw i t ht h es e to f v e r t i c e s v a n d t h es e t o f e d g e s e ，a n d c = 1 ，2 ，忌) ，as e t o f kc o l o r s ap r o p e rk - e d g e - c o l o r i n go fgi sam a p p i n gf r o mei n t ocs u c ht h a tn o a d j a c e n te d g e sr e c e i v et h es a m ec o l o r i fgh a sap r o p e rk - e d g e - c o l o r i n g t h e ngi ss a i dt ob ek - e d g e - c o l o r a b l e t h ec h r o m a t i ci n d e x d e n o t e db y x 7 ( g ) ，i st h el e a s tn o n - n e g a t i v ei n t e g e r 后s u c ht h a tgi s 南一e d g e e o l o r a b l e a ne d g e - l i s t - a s s i g n m e n tlo fgi sas e to fl i s t so fc o l o r sw h i c ha s - s i g ne a c he d g eeo fgal i s to fc o l o r sl ( e ) i fgh a sap r o p e re d g e - c o l o r i n g 妒s u c ht h a t 妒( e ) l ( e ) f o re v e r ye e ，t h e ng i ss a i dt ob e l e o l o r a b l e i fgi sl - c o l o r a b l ef o re v e y ye d g e f i s t - a s s i g n m e n tlw i t h j 己( e ) l kf o re v e r ye e ，t h e nw es a yt h a tg i sk l i s t - e d g e - c o l o r a b l e ， o rk - e d g e - c h o o s a b l e t h ee d g ec h o i c en u m b e r , o r , l i s t - c h r o m a t i ci n d e xo f g ，d e n o t e db yx ；( g ) ，i st h el e a s tn o n n e g a t i v ei n t e g e rks u c ht h a tg i s k - e d g e - c h o o s a b l e o n e d g e - c o l o r i n go f g r a p h s ，v i z i n gm a d e ag r e a tb r e a k t h r o u g hi n1 9 6 4 h ep r o v e dt h a t ( g ) = ( g ) o rx 7 ( g ) = + 1 t h i sf a m o u st h e o r e m d i v i d e sf i n i t es i m p l eg r a p h si n t ot w oc l a s s e sa c c o r d i n gt ot h e i rc h r o m a t i c i n d i c e s ，n a m e l mag r a p hi ss a i dt ob eo f c l a s sli f x 7 ( g ) = ( g ) ；o f c l a s s 2 ，o t h e r w i s e f o l l o w i n gp r e c e d e n tw o r k s ，t h i sd i s s e r t a t i o ns t u d i e sc l a s s i f i c a t i o np r o b - l e m so fp l a n a rg r a p h s t h em a i nr e s u l t so b t a i n e di nt h i sd i s s e r t a t i o n sm a y b es u m m a r i z e da sf o l l o w s ： ( 1 ) i fg i sap l a n a rg r a p hw i t hm a x i m u md e g r e e6a n dw i t h o u t7 - c y c l e s t h e ng i so f c l a s s1 ， ( 2 ) l e tg b eap l a n a rg r a p hw i t hm a x i m u md e g r e e5 gi so fc l a s s1 一n 一 i f 0 1 1 eo f t h ef o l l o w i n gc o n d i t i o i l sh o l d s ： ( i ) gc o n t a i n sn o4 一c y c l e ；( i i ) gc o n t a i n sn o5 - c y c l ea n dn oa d - j a c e n tt r i a n g l e s 。 ( 3 ) i f g i sa p l a n a rg r a p h w i t hm a x i n l u l nd e g r e e4a n d w i t h o u tc y c l e s o f l e n g t hf r o m4 t o1 2 t h e ngi so f c l a s s1 o ne d g e c h o o s a b i l i t yo fp l a n a rg r a p h s ，t h i sd i s s e r t a t i o no b t a i n e da m o d e r a t er e s u l ta sf o l l o w s ( 4 ) i f a p l a n a rg r a p hgw i t h ( g ) 5a n d6 c o n t a i n sn oa d j a c e n t t r i a n g l e s ，t h e nx ；( g ) = ( g ) + 1 k e yw o r d s ：p l a n a rg r a p h ，c h r o m a t i ci n d e x ，l i s t - c h r o m a t i ci n d e x ，m a x i m u n ld e g r e e 一一 学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他 机构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均 已在论文中作了明确的声明并表示了谢意。 研究生签名 枷梧、扬 学位论文使用授权声明 日翰：弘帕t 。限 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有 权保留送交论文的复印件和电子文档，允许沦文被查阅和借阅，可以采用影 印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同方 式在不问媒体上发表、传播论文的全部或部分内容。保密的学位论文在解密后 遵守此协议。 研究生虢修孑莨尚导师虢互乏面隰彦6 日 一、绪论 ( 一) 、基本概念 一、绪论 在本节中，我们定义一些本学位论文中要用到的图论的基本术语与符号一 个有序对g = ( ue ) 称为一个无向图，其中v 是一个有限集合，e 是y 中的不同元 素的无序对的集合y 中的元素叫做图g 的顶点，e 中的元索叫做图的边通常 用v ( g ) 、以g ) 分别表示图g 的顶点集合、边集合没有重边和环的图叫做简单 图除非特别指出，本文研究的图均指有限简单无向图如果能将图g 画在平面上， 使得它的边仅在端点处才可能相交，则称图g 是可平面图图的这种平面上的画 法称为图的平面嵌入，或称为平面图 常用u ，t j 表示g 中的点，e ，g 中的边，g 中的面若边e = 缸口e ( g ) ，则 说h ，u 在g 中相邻，或n 和 互为邻点；这时又说u 和u 是e 的端点t ，的全体邻点所形 成的集合叫做v 的邻域，记作( ) ，设acy ( g ) ，称n ( a ) ：= u ( 口) 为a 的邻 域若点u 是边e 的端点，则说u 与e 在。中相关联，若顶点t ，( 边e ) 在面，的边界上，则 说u ( e ) 与，在g 中相关联称有一个公共端点的两条边相邻，以及至少有一条公共 边的两个面相邻设口是一个顶点，与口相关联的边的条数叫做口的度数，记作d ( u ) g 中的点的最小和最大的度数分别记作占( g ) 和( g ) ( 或) 若d ( v ) = k ( d ( ) k ， d ( 口) 七) ，则称t ，为一个k 点( 角+ 点，k 一- 点) 我们把一个与v 相邻的k 一点，叫作 的 一个七邻点用d k ) 表示u 的k 邻点的个数 设图g 是平面图，常用f ( g ) 表示面集合对于，f ( g ) ，用6 ( ，) 表示围绕 面，的闭途径把途径6 ( ，) 的长度称为面，的度，记为d ( ，) 若d ( f ) = k ( d ( ，) k ， d ( y ) 幼，则称，为一个k 一面( 矿面，k - - 面) 若一个面的边界是一个圈，则称这个 面是一个简单面若平面图g 是2 边连通的，则它的每个面的边界都是一个圈，常 用这个圈的顶点序列来表示这个面对于三面，= 0 1 2 2 0 3 ，为强调它的关联特性， 常用度序列( d ( x ，) ，d ( z 2 ) ，d ( x 3 ) ) 表示， 如果顶点。与圈c k = z 1 0 2 z 。的每一个顶点都相邻，则称与g 构成一个 以。为心的n 轮g 的边叫做这个轮的周边，z 称为轮心或中心在一个n 一轮的 外圈上任意删去一条边，得到一个n 扇，这时轮心就变成了扇心一个面，与一 个n 轮相邻，指的是面，与该轮至少有一条公共的周边若只有一条公共周边，称 、绪论 它们弱相邻，若至少有两条公共周边，则称它们强相邻 本文所用术语和符号基本上与文献 1 中一致本节中未介绍的其他图论术 语将在必要时予以阐述 ( - - ) 、边染色问题的研究概况与本文的研究工作 图的染色理论是图论中最霞要的分支之一，在无线通讯频道分配、舰队维 护、任务分派、交通定向等诸多领域都有着广泛的应用，见文献 2 】本学位论文 主要研究了平面图得边染色 若有一个映射：e ( g ) 一 1 ，2 ，七) ，使得对任意相邻的两条边e l e 2 e ( g ) ，有妒( e 1 ) ( e 2 ) ，则称是图g 的一个正常七边染色定义图g 的边色数 为( g ) 一仃“竹 甜g 有一个正常南边染色 若g 有一个正常七边染色，则称g 是七一 边可染的除非特别声明。图g 的七边染色均指正常七边染色 1 9 6 4 年，v i z i n g 证明了如下著名定理： 定理1 1 【3 】若g 是简单图则 a ( g ) 兰x 7 ( g ) a ( g ) + 1 这一基本定理引出了简单图的分类问题称( g ) = a ( g ) 的简单图g 为第一 类的，其余的简单图为第二类的图的分类问题就是想要给出第一类( 等价地，第 二类) 图的特征刻画在将近半个世纪的漫长岁月里，人们一直在为解决简单图的 分类问题做着不懈的努力解决一般的分类问题似乎还有漫长的路要走，因此人 们特别关心平面图的分类问题如果把图的分类问题限制在外平面图上，那么问 题已完全解决，看下面的定理1 2 定理1 21 4 一个外平面图是第2 类的，当且仅肖它是一个奇网 对一般的平面图，早在1 9 6 5 年，v 1 2 j a - i g 就证明了下述重要的结果 定理1 3i s a ( g ) 8 的简单平面图g 是第一类的 在 5 中，z i n g 还举例说明了这样一个重要事实：对于 2 ，3 ，4 ，5 ) ，同时 存在着两种类型的简单平面图1 9 6 8 年，他最终提出了如下的平面图猜想： 一2 一 、绪论 猜想1 1 问( 平面图猜想) 最大度为6 或7 的平面图是第一类的 时隔三十多年之久，z h a n g ( 2 0 0 0 ，【7 ) ，s a n d e r s 和z h a o ( 2 0 0 1 ，e 8 ) 独立地证明了 平面图猜想对x ( g 1 = 7 是正确的即有 定理1 4 【7 b 】最大度为7 的平面图是第一类的 于是解决平面图猜想只需考虑a ( o ) = 6 的情况2 0 0 3 年，周国飞证明了： 定理1 5 1 9 1 a ( c ) = 6 且不含有k 圈( 对某个后 3 ，4 ，5 ) 的简单平面图g 是第一 类的 新近h 月华和王维凡给出了如下结果： 定理1 6d 0 设g 是最大度为6 的平面图，如果它满足以下条件之一： ( 1 ) g 不含弦4 一圈； ( 2 ) g 不含弦5 - 圈和弦6 - 圈； ( 3 ) g 不含6 一圈， 则g 是第一类的 在文献 1 0 】的最后注记中，他们指出：目前还不知道a ( g ) = 6 且不含有七一 圈( 对某个k 7 ) 的简单平面图g 是否是第一类的本文证明的第一个主要结果 是： a ( c ) = 6 n 不含有7 圈的简单平面图g 是第一类的 这一结果显然是对平面图猜想的进一步支持 在平面图的分类问题中，对予7 的平面图，已经完全确定它们都是第一 类的，对于= 6 的平面图是否存在第二类的这一问题还没有解决对于 2 ，3 ，4 ，5 ) 的平面图，既存在第一类的，又存在第二类的给出 2 ，3 ，4 ，5 ) 的平 面图是第一类或第二类的特征刻画，在平面图的分类中具有重要意义对= 2 的 平面图的分类问题已经完全解决，即所有的奇圈都是第二类的，所有的偶圈和路 都是第一类的对3 的平面图，1 9 7 4 年s f i o r i n i i 正明了如下定理： 定理1 7 【1 1 】令g 是最大度为，围长为g 的平面图如果g 满足下列条件之一： ( i ) 3 且岔8 ； 一3 一 一、绪论 ( i i ) a 4 且9 5 ； ( i i i ) a 5 且g 4 ； ( i v ) a 8 且g 3 那么g 是第一类的 1 9 9 9 年p l a m 等人证明了如下结果： 定理1 8 【1 2 】令g 是最大度为的平面图。若g 满足下列条件之一： ( 1 ) a 5 且g 不含4 一圈和5 一圈； ( 2 ) 5 且g 不含4 一圈，并且g 中没有两个三角形有公共的顶点； ( 3 ) a 4 且g 不含4 到1 4 一圈； ( 4 ) 4 且g 不含4 、5 、6 圈，并且g 中没有两个三角形有公共的顶点， 则g 是第一类的 本文在第三章和第四章对p l a m 等人的以上结果进行了部分改进，证明的主 要结果是： 令g 是最大度为的平面图，若g 满足下列条件之一： ( 1 ) a = 5 且g 不含4 一圈； ( 2 ) a 一5 且g 不含5 一圈，并且g 中没有相邻三角形； ( 3 ) a = 4 且g 不含4 到1 2 一圈， 则g 是第一类的 映射l 称为图g 的一个边色列表，如果它指定g 的每条边e 一个颜色集合l ( e ) 若g 有一个正常的边染色妒，使得每一条边e 满足妒( e ) l ( e ) ，则称g 为厶边可染 的，或称妒是g 的一个l 边染色若对任意表l ，i l ( e ) i = 七对每一条边e e ( g ) 成 立，且g 是l 边可染的，则称g 是七边可选择的g 的边选择数，或者列表边色 数( g ) 是使得g 是后边可选择的最小的整数七 下面介绍两个著名的边列表染色猜想： 猜想1 2d 3 如果g 是一个多重图，则弼( g ) = x ( g ) 这就是著名的l c c 猜想对于二部重图【1 4 】、奇阶完全图1 1 5 、多重圈【16 】、 外平面图 1 7 】、1 2 可嵌入非负特征曲面上的图d s 等，已证明猜想1 成立 v j i z i n g 提出了下面弱化的边列表染色猜想( 见文献 1 9 ) ： 一4 一 一、绪论 猜想1 3 每一个图g 是( + 1 ) 边可选择的 h a r r i s 2 0 11 9 8 4 证明：如果g 是一个3 的图，那么x ，( g ) 2 a 一2 这隐含着 猜想2 对于= 3 f l t j 图成立j u v a n m o h a r 和s k r e k o v s k i 2 1 】解决了= 4 的情形对 于完全图【1 5 1 ，围长至少为8 a ( 1 n + 1 1 ) 的图i ，9 的平面图【2 2 】等，己证明猜 想2 成立设3sk 6 是一个固定整数，对于不含k 圈的平面图 2 3 - 2 6 ，也已证明猜 想2 成立王和李1 2 7 证明：每一个5 且没有相交3 圈的平面图是( + 1 ) 边可选 择的 本文将证明的第三个主要结果是： 每一个5 和6 ，且不含桕邻三角形的平面图是( + 1 ) 边可选择的 一5 一 、最大度为6 的甲面图的分类 二、最大度为6 的平面图的分类 对于平面图猜想，最大度为7 的情形已被解决，可参考文献 7 ，8 】最大度 为6 的情形，目前仍然是一个公开闯题该问题目前尽管还没有被解决，但已经取 得一些有意义的进展，参考文献r 9 ，1 0 本节在前人的基础上给出了一个关于最 大度为6 的平面图分类问题的结果 定义2 1 给定图g ，若存在一条路通过图中每个顶点一次且仅一次，这条路称 为h a m i l t o n 路若存在一条回路，通过图中每个顶点一次且仅一次，这条回路称 为h a m i l t o n 圈或h a m i l t o n 匐路 用c ( g ) 表示图g 的连通分支的个数 引理2 1d 3 如果g 有- - + h a m i l t o n 圈，那么对v ( a ) 的任何非空子集s ，都有 c ( g s ) l s 定理2 。1 在图1 - 1 所示的备图中均不存在h a m i l t o n - 圈 g 1 $ g 4 图1 1 ：其中黑方块代表同一个点，在以后的图中就不再说明 一6 一 二、最大度为6 的平面图的分类 证明：假设在g j 中存在h 锄i l t d n 一圈，则g j 应满足引理2 1 ，其中j = l ，2 ，3 ，4 然而， 取最= v k ，u k ，峨) ( 七= 1 ，2 ) ，最= m ，蛳 0 = 3 ，4 ) ，则有 c ( g k s k ) = 4 3 = i 鼠l ( 七；1 ，2 ) c ( g t 一最) = 3 2 = i 最i ( i = 3 ，4 ) 这与引理2 1 相矛盾，从而以上各图中均不存在h a m i l t o n 圈口 注意：若一个图中不存在h a m i l t o n - 圈，那么删去任意条边后仍然不存 在h a m i l t o n - 圈 同理利用引理2 1 容易证明如图2 2 所示的结构中不含7 一圈 图2 2 定理1 1 揭示了参数x ( g ) 与( g ) 之间的重要联系研究图的分类问题的一个 重要途径是去研究“色临界图”的结构性质。如果图本身是第二类的。但删去 它的任何一条边之后，所得到的图是第一类的，则称它是一个色临界图以下是 有关色临界图的结构性质的3 个引理这3 个引理在以后的章节中也要用到 引理2 2 【5 1m 痂g 的邻接性引理) 设g 是最大度为的色临界图( 简称g 是色临 界的) ，e ( g ) ，d ( v ) = 七，贝u 有 ( 1 ) 若k 2 一( i 1 4 + 去6 ) = 去 o ( 5 2 ) 下面考虑t ，至少与一个4 一一点相邻的情况 ( 5 2 1 ) 设与t j 相关联的3 - 面正好有4 个 若u 不与8 + 面相关联，则一定出现如图2 6 所示的子结构，由r 1 、r 4 i 、r 4 4 及 r 4 5 1 得 伽( ) = ” ) 一” ，) + ”( 一”) 2 一( 1 + ；3 + 互1 ) + 南5 = 0 ； 若可与8 + 面相关联，则由k l 、r 4 i 、r 4 ，4 、r 4 5 2 及r 4 5 3 得 叫7 ( u ) = 伽( 口) 一叫扣- - ) + w ( - - - , t ，) 2 一( ；4 + ；2 ) + ；= o 其中等号成立时的结构如图2 9 所示 66 图2 - 9图2 1 0 66 图2 1 l ( 5 2 2 ) 设与 相关联的3 一面正好有3 个 若 不与8 + 面相关联，则一定出现如图2 1 0 所示的子缔构此时由r 2 、r 4 1 、 r 4 2 及r 4 4 得 ”7 ( ) - - w ( u ) 一叫扣一) 2 一( ；2 + ；2 + i 1 ) = o 1 6 一 二、最大度为6 的平面图的分类 若口与8 + - 面相关联，由r 2 、r 4 1 、r 4 2 、r 4 4 及r 4 6 得 埘 ) = 叫扣) - w ( u _ ) + 叫( - t ，) 2 一( 1 + 互1 + 否1 2 ) + ：= o 其中等号成立时的结构如图2 一l l 所示 ( 5 2 3 ) 若与u 相关联的3 一面不超过两个，则p a r l 、r 2 、r 3 1 及r 4 1 r 4 4 知 加7 ( 秽) = 伽( 口) 一伽 _ ) 2 一( 1 + 互1 + 否1 ) = 石1 0 至此，v y ( g ) ，w 7 ) 0 验证完毕 检验面上的新权 ( 1 ) 对任意的3 一面，由r 3 1 及r 4 1 r 4 4 得 埘( 厂) = ( ，) + ( + ，) = - - 1 + 1 = 0 ( 2 ) r v 任意的4 - 面、5 - 面或6 一面，都有( 厂) = 叫( ，) 4 4 = 0 ( 3 ) 对任意的8 + - i l i i f ，设d ( y ) = 七( 8 ) 6 图2 1 2 ( 3 1 ) ，向与它相关联的点转移的权至多为；，易见这样的点不超过嘲个， 如图2 - 1 2 所示在图2 1 2 中啦至多关联2 个3 一面若与，相关联且从，得到；的点 有蝗j 个，则 州，) = 叫) 一蚶一) ( k - 4 ) _ ；r 争2 七一4 一；字 o 1 7 一 - 二、最大度为6 的平面图的分类 注j 敖至： ( i ) ，与5 一轮或者与5 - 扇的每个公共点至多从，得到 当与，相邻的5 一轮和5 扇上出现3 点时，由r 3 2 1 、 ，向这样的轮心和扇心上转移的权至多为 ( i i i ) 当与，相邻的5 一轮和5 扇上不出现3 点时，由r 3 2 2 、 ，向这样的轮心和扇心上转移的权为丢 r 3 2 3 及r 3 3 知： r 3 2 4 、r 3 3 知： 其次，设e 是，与一个5 轮或一个5 扇的公共边，若与e 相关联的5 轮或5 ，扇 上出现3 点，则由引理2 4 ( 3 ) 知，上与e 相邻的边就不再与5 轮或5 扇相关联，除 非，与5 一扇f 强相邻( 这时设8 l ，e 2 是，与f 的两条公共边，贝l j 在，上与e 1 ，e 2 是最与最的 两条公共边，则在r 上与e 。， ( 3 2 ) 若，只与出现3 点的5 轮和5 一扇相邻，则与，相邻的5 - 轮和5 一扇的总个数 至多为【刳个，由( i ) ( i i ) 及七8 有 ”( ，) = t ，( ，) - w ( f 一) 一4 ) 一( 七+ l 鲁j ) ( 七一4 ) 一( 鲁- 4 - ) 0 喾二氯 图2 - 1 3 ( 3 3 ) 若，不与出现3 点的5 轮和5 - 扇相邻，则与，相邻的5 一轮和5 一扇的总个数 至多为后个此时，若与，相邻的5 一轮与3 一面相邻，如图2 1 3 所示，则，向啪转移刍， 向。，至多转移 ，向”：至多转移又冈为 + + 袅 ( 七一4 ) 一( 七+ i 1 k ) = 一4 0 结合上述3 种情形，易见对任意的8 + 一面，都有 ( ，) = w ( f ) 一w ( f + ) 0 这样，对任意的f f ( g ) 都有w 7 ( ，) 0 定理2 2 证毕 一1 8 三、最大度为5 的甲面图的分类 三、最大度为5 的平面图的分类 在前一节中我们讨论了最大度为6 的平面图的分类问题，在本节中我们将要 讨论最大度为5 的平面图的分类问题 由上一节中的引理2 2 、2 3 、2 4 可得如下推论： 推论3 1 若g 是一个5 色临界平面图，则在a 中出现的3 一面只可能是以下几种 类型： ( 2 ，5 ，5 ) 一面，( 3 ，4 ，5 ) 面，( 3 ，5 ，5 ) - 面，( 4 ，4 ，4 ) 一面，( 4 ，4 ，5 ) 一面，( 4 ，5 ，5 ) - 面，( 5 ，5 ，5 ) 一面 定理3 1 若图g 是最大度为5 且不含4 圈的平面图，则g 是第一类的 证明：假如定理3 1 不成立，即存在a = 5 且不含有4 一圈的第二类平面图，在这 类图中选取一个边数尽可能地少的平面图，记为g ，则g 是5 色临界的且不含 有4 罔若g 有割点，则从i e ( g ) 的极小性出发易证是g 第一类的，得到矛盾因此， g 是2 。连通的j 1 6 ( g ) 2 2 以下的证明方法和目的是在v ( g ) u f ( g ) i - 定义一个权函数 ( z ) ，然后运用 “d i s c h a r g e ”方法导出矛盾，从而完成定理3 1 的证明 易得 首先，对v z v ( g ) u f ( g ) ，令 ) = d ( z ) 一4 由欧拉公式以及熟知的公式 d ( 。) = 2 1 e ( g ) i = d ( 。) $ y ( 口)z f ( g ) 叫( z ) = 一8 z e v ( g ) uf ( g ) ( 3 1 ) 将在v ( g ) uf ( g ) 的元素之间规定一个“d i s c h a r g e ”规则进行权的转移而得 到一个新的权函数钮7 ( z ) 因为权是在y ( g ) uf ( g ) 的元素之问进行转移的，所以 t o 协) = ”( z ) = 一8 = e v ( g ) u f ( g )z ，( g ) u l f ( g ) 一1 9 一 ( 3 2 ) 三、最大度为5 的甲面图的分类 另一方面，按照即将给出的规则，将证明 7 ( z ) o 在v ( g ) u f ( g ) 上处处成立，从 而得到完成证明所要的矛盾 所需的“d i s c h a r g e ”规则定义如下： r 1 每个2 点从它的每个邻点得到1 r 2 对于任意的3 点口，首先，t j 从与它相关联的每个5 + 面得到 ；然后，如 果口的3 个邻点都是5 点，那么v 从与它相邻的每个5 点得到考否则，u 从与它相邻 的每- t - 5 - 点得到杀 r 3 每个与2 点相邻的5 点从与它相邻但不与它关联同一个( 2 ，5 ，5 ) 一面的每 个5 点得到 r 4 0 g 的每个3 一面从与它相邻的每个5 + 面通过它们的每条公共边得 到；因此，如果一个3 面与一个6 + 面有两条公共边，则该3 一面从该6 + - 面总共得 到；( 5 一面与3 面不可能有两条公共边) r 4 1 如果一个3 面只与一个5 点相关联，那么该3 一面从这个5 一点得到； r 4 2 如果一个3 面与两个5 点相关联，那么，该3 面从与它相关联的每 个5 点得到i 1 r 4 3 如果一个3 面与三个5 点相关联，那么，该3 面从与它相关联的每 个5 点得到鲁 r 4 4 由推论3 1 ，不与5 点相关联的3 面只有( 4 ，4 ，4 ) 面设，是这样一个( 4 ，4 ，4 ) 一 面，则，从( ，) ) y ( ，) 中的每个5 一点得到击 用t ，佃一) 表示从z 转移出的总权数，而伽( 一。) 则表示向茹转入的总权数由 于g 不含4 圈，所以g 中不含相邻的三角形于是与g 的任意一- 个点u 相关联的三 角形的个数至多有【掣个，且与三角形相邻的面都是5 + - 面下面将验证：对任 意的z v ( g ) uf ( g ) 都有铷7 ( z ) 0 一检验顶点上的新权 旨先，根据引理2 3 ，2 - 点只与5 一点相邻，3 - 点只与4 + - 点相邻因此 ( 1 ) 对于任意的2 - 点 ，m r l ， ( ) 一w ( v ) + ( 一u ) = - - 2 + 1x2 = 0 2 0 三、最大度为5 的平面图的分类 ( 2 ) 对于任意的3 - 点钉，注意到它至少与两个5 点相邻，两个5 + 一面相关联 由r 2 知。 t 正，7 p ) = 叫( u ) + 删( ，u ) 一l + ( 未2 + 亏1 2 ) = o ( 3 ) 对于任意的4 一点u ，易见 伽p ) = w 0 , ) = 0 ( 4 ) 设 是一个5 一点 如果u 与一个2 - 点相邻，由引理2 4 e o ( 1 ) 知，口的其他邻点都是5 一点由r 1 ，r 3 及r 4 1 至r 4 3 知 ”( ”) = 叫 ) 一” 一) + ”( 一u ) 1 一( 1 + ；+ 杀) + ；3 = 0 由引理2 2 ( 1 ) 知，钉至多可与两个3 一点相邻当f 只与一个3 点相邻时， 仍由引理2 2 ( 1 ) 知， 至少与3 - 5 - 5 一点相邻，至多与1 + 4 一点相邻，并由引理2 4 ( 2 ) 失1 r l 在( ) ) 巾没有2 - 点因此由l 也、2 3 i ：r 4 1 至r 4 4 知 ”伽) = ”( ) 一伽( ”一) 1 一( 杀+ ；+ 蠢) = - 1 o 当 正好与两个3 点相邻时，由引理2 2 ( 1 ) 知，它的其他的邻点都是5 一点，并由 引理2 4 ( 2 ) 知在( ( 口) ) 中没有2 点再由引理2 3 5 n 引理2 4 知，这两个3 一点的邻 点也都是5 点由r 2 、r 4 2 和r 4 3 知 伽7 。) = 埘 ) 一”。一) 1 一( ；2 + ；2 ) = 亏1 o 如果秽只n 4 + 一点相邻，由引理2 3 ( 1 ) ，口至少- 与2 + 5 一点相邻，从而至多 与3 个4 点相邻由r 3 和r 4 1 至r 4 4 知 ”7 ) = 伽扣) 一彬扣一) 1 一( 否1 + i 2 + ；十去) = ； o 至此，讹y ( g ) ，w 7 ( u ) 0 验证完毕 一2 l 一 兰、最大度为5 的甲面图的分类 一检验面上的新权 ( 1 ) 如果一个3 一面，至少与一个5 一点相关联，那么，由r 4 0 至r 4 3 ，有 叫7 ( ，) = z o ( f ) + w ( - - - * f ) = 一1 + ( 亏3 + 亏2 ) 一。 如果一个3 - 面，不与任何5 一点相关联，根据推论l 知，一定是1 个( 4 ，4 ，4 ) 一面由 引理2 4 中( 1 ) 知：( y ( ，) ) y ( ，) 中的点都是5 - 点再由g 中不含4 一圈和相邻的3 - 面 知l ( y ( ，) ) y ( 删= 6 因此，由r 4 0 ： f i r 4 4 得 叫( ，) = 叫( ，) + 伽( 一门= 一1 + ( ；3 + 1 6 ) = o ( 2 ) 对任意的5 + 一面f ，设d ( ，) = 七( 5 ) 若，与1 + 2 一点u 相关联，则同时 与u 和，相关联的两条边或者与同1 个3 一面相关联，或者同时都不与3 - 面相关联 若，与一个3 点“相关联，则i 司时与u 和厂相关联的2 条边中，至多有1 条边与1 个3 一面 相关联根据r 2 和r 4 o 知：从，转移出的权至多为 xk 因此由尼5 得 7 ( ，) = ( ，) 一j t o ( f - - 0 ( k - - 4 ) 一i k = i 4 k 一4 0 这样，对任意的f f ( g ) 都有 ( ，) 0 定理3 1 证毕 定理3 2 若图g 是最大度为5 且不含5 圈和相邻三角形的平砸图，则g 是第一类的 证明：假如定理3 2 不成立，即存在a 一5 且不含有5 圈和相邻三角形的第= 类 平面图，在这类图中选取一个边数尽可能地少的平面图，记为g ，则g 是5 色临 界的若g 有割点，则从i e ( g ) l 的极小性出发易证是g 第一类的，得到矛盾因此， g 是2 连通的且d ( g ) 2 以下的证明方法和目的是在v ( g ) uf ( g ) 上定义一个权函数叫( z ) ，然后运用 “d i s a 。r g e ”方法导出矛盾。从而完成定理3 2 的证明 首先，对v 窭v ( c ) u f ( g ) ，令 ) = d ( x ) 一4 由欧拉公式以及熟知的公式 d ( 。) = 2 e ( g ) i = d ( z ) x e v ( g )z e f ( g ) 一2 2 _ - - 、最大度为5 的平面图的分类 易得 ”( z ) = 一8 z y ( 回u f ( g ) ( 3 3 ) 将在v ( g ) u f ( g ) 的元素之间规定一个“d i s c h a r g e ”规则进行权的转移而得 到一个新的权函数彬 ) 凼为权是在y ( g ) u f ( g ) 的元素之问进行转移的，所以 ” ) = ”( 。) = 一8 y ( g ) uf ( g ) x e v ( g ) uf ( g ) 另一方面，按照即将给出的规则，将证明叫( 。) o 在v ( g ) u f ( g ) 上处处成立，从 而得到完成证明所要的矛盾 所需的“d i s c h a r g e ”规则定义如下： r i 每个2 点从它的每个邻点得到1 r 2 设 是一个3 点如果7 2 的3 个邻点都是5 点，那么 从与它相邻的每个5 点 得到；否则，钞从与它相邻的每个5 点得到 r 3 g 的每个3 面从与它相邻的每个6 + 面透过它们的每条公共边得到；因 此，如果一个3 面与一个7 + 面有两条公共边，则该3 面从该7 + 面总共得到；( 6 面 与3 。面不可能有两条公共边) 用扛一) 表示从转移出的总权数，而 ( 一z ) 则表示向。转入的总权数由 于g 不含带弦的4 圈，f 1 0 g 中不含相邻三角形，于是与g 的任意一个点口相关联的 三角形的个数至多有i ! 1 个又因为g 不含5 圈，所以与三角形相邻的面都是 6 + - 面下面将验证：对任意的g v ( g ) uf ( g ) 都有 7 ( z ) 0 检验顶点上的新权 首先，根据引理2 3 ，2 点只与5 一点相邻，3 点只与4 + 点相邻因此 ( 1 ) 对于任意的2 - 点口，由r 1 ， w 7 ) = w ( v ) + 叫( ) = - - 2 + 1 2 = 0 ( 2 ) 对于任意的3 一点u ，注意到它至少与两个5 一点相邻，由r 2 知， 7 扣) 一w ( v ) + t ，( ， ) = - - 1 + ( x2 ) = 0 ，或者 一2 3 三、最大度为5 的甲面图的分类 w 7 ) = w ( v ) 1 - 叫( ) = 一1 + ( 3 ) = 0 ( 3 ) 对于任意的4 一点 1 ，易见 w 扣) 一w ( v ) = 0 ( 4 ) 设v 是一个5 点 如果u 与一个2 - 点相邻，由引理2 4 ( 1 ) 知， 的其他邻点都是5 - 点由r 1 知 伽 ) 一叫( 口) 一w ( v ) = 1 1 = 0 由引理