5-连通图的可收缩边的分布

王振刚，齐恩凤

（山东大学数学学院，山东 济南 250100）

5-连通图的可收缩边的分布

王振刚，齐恩凤

（山东大学数学学院，山东 济南 250100）

图的可收缩边问题对于研究图的结构和证明图的某些性质有着重要作用。本文给出了5-连通图中某些最长圈可收缩边的分布情况，用树型结构理论进行分类讨论，得到如下结论：不含2-断片的5-连通图的最长圈上至少有三条可收缩边。

5-连通；可收缩边；最长圈

近年来，连通图中的可收缩边的存在性和分布情况成为人们十分关注的课题［1］。Tutte［2］利用3-连通图的可收缩边给出了3-连通图的结构特征，并证明了每一个阶数至少为5的3-连通图都含有可收缩边。Thomassen［3］利用3-连通图可收缩边的存在性，通过归纳法给出了Kuratowski定理一个简洁的证明。更多的关于可收缩边的结果由Krisell［4］给出。由此可以看出，一个图的可收缩边是探讨图的结构、利用归纳法证明图的某些性质的有力工具。

本文进一步考虑某些5-连通图上最长圈上可收缩边的情况，改进了杨朝霞［5］的结果，得到如下结论：不含2-断片的5-连通图的最长圈上至少有3条可收缩边。

1 相关概念

本文考虑的都是有限简单图，所讨论的5-连通图G都是连通度k（G）＝5的图。

V（G）和E（G）分别表示G的顶点集和边集。设e＝xy∈E（G），我们将顶点x，y去掉，并将与这两个顶点相关联的边去掉，然后增加一个新顶点，将新顶点与原顶点x，y相邻接的顶点邻接，如此我们叫做把边e收缩，记为G／e。如果收缩e后，G仍是5-连通的，则e是G的可收缩边。如果去掉G中一个5个点的点集T后，G不连通，则称T为G的5-点割。显然，若e是G的不可收缩边，则G中存在一个包含e的两个端点的5-点割。G的所有可收缩边记为EC（G）。

设A，B⊂V（G），A∩B＝Ø，A≠Ø≠B，定义＜A，B＞＝｛xy∈E（G）：x∈A，y∈B｝。用N表示V（G）的非空子集，则N在G中的导出子图用［N］表示。G中两点x与y之间的路记为（x，y）-路。若e＝xy∈E（G），且xy∉EC（G），则易知G中存在包含x与y的5-点割T，我们称G-T的各个连通分支为断片。设E0⊆E（G）－EC（G），若xy∈E0，设T是包含x，y，的5-点割，则称T为E0-点割，称G-T的各个连通分支为E0-断片。如果E0-断片不包含其他E0-断片作为它的真子集，则称它为E0-端片。特别地，若A是一个断片，且｜A｜＝2，则称A为2-断片。

2 5-连通图的最长圈上可收缩边的分布情况

2008年，杨朝霞已经证明了下述两个引理：

引理1［5］设P：x＝x1x2…xn是5-连通图G的一条最长（x，y）-路。若xixi＋1是一条不可收缩边，且S＝｛xi，xi＋1，u1，u2，u3｝是其相应的5-点割，则G-S的每一个断片至少包含P上的一个点。

引理2［5］设G是5-连通图且不包含2-断片。P：x＝x1x2…xn＝y是G的一条最长（x，y）-路。若路P上任一顶点xi都满足以下两个条件之一，则P至少包含一条可收缩边：

（1）d（xi）≥6；

（2）若d（xi）＝5，则［V（P）］中无3-圈包含它。

本文将对杨朝霞的结果进一步改进：

引理3设G是5-连通图且G不包含2-断片。P：x＝x1x2…xn＝y是G的一条最长（x，y）-路。若路P上任一顶点xi都满足以下两个条件之一，则P至少包含两条可收缩边：

（1）d（xi）≥6；

（2）d（xi）＝5，则［V（P）］中无3-圈包含它。

证明：反证法。根据引理2，假设P上只有一条可收缩边，不妨设为xjxj＋1。设E0＝E（P）－xjxj＋1，则对于每一条边xixi＋1（i≠j），都有相应的E0-点割S＝｛xi，xi＋1，u1，u2，u3｝的导出子图［S］包含它，且对于G-S的每一个连通分支都是E0-断片。设S′是G的一个E0-点割，A′是G-S′的一个E0-断片，B′＝G－A′－S′是其他E0-断片之和。显然xjxj＋1∈［V（A′）∪S′］或［V（B′）∪S′］。不失一般性，我们可设xjxj＋1∈［V（B′）∪S′］，则xjxj＋1∉［V（A′）∪S′］。既然每一个E0-断片都包含一个E0-端片作为它的子集，我们可设A是A′的一个E0-端片，且B＝G－A－S是其他E0-断片之和。既然A是A′的子集，显然，xjxj＋1∉［V（A）∪S］。由引理1可知E（P）∩＜A，S＞≠Ø，设v1u∈E（P）∩＜A，S＞，其中v1∈A，u∈S。既然v1u∈E0是不可收缩边，设其对应的E0-点割为T＝｛u，v1，w，s，t｝，令G-T＝C∪D，其中C≠Ø≠D。易知u∈S∩T，v1∈A∩T。设

首先，我们证明A∩C＝Ø。

假设A∩C≠Ø。此时X1是G的一个点割。此时必有｜X1｜≥6成立，否则，有｜X1｜＝5成立。既然uv1∈E0∩E（［X1］），则X1是G的E0-点割，A∩C是G-X1的E0-断片（或E0-断片的和），与A是G的E0-端片相矛盾。故｜X1｜≥6。注意到｜S｜＋｜T｜＝｜X1｜＋｜X3｜＝10，故｜X3｜≤4，由G是5-连通图可知B∩D＝Ø。我们说D∩S≠Ø，否则，有D＝D∩A，则D是包含在A中的E0-断片，与A是G的E0-端片相矛盾。故D∩S≠Ø。此时又分以下几种情况：

（1）如果B∩T≠Ø，｜X3｜≤4，则｜B∩T｜＝1或2，

（1.1）若｜B∩T｜＝1，则｜S∩T｜＝1或2。

若｜S∩T｜＝2，则｜A∩T｜＝2，｜S∩D｜＝1，｜S∩C｜＝2。此时｜X2｜＝5，则A∩D＝Ø，否则A∩D是G-X2的E0-断片（或E0-断片的和），与A是E0-端片矛盾。｜D｜＝｜S∩D｜＝1，设D＝｛t1｝，则t1uv1t1是G的3-圈。根据引理1，t1∈V（P），d（t1）＝5，矛盾。

若｜S∩T｜＝1，则｜A∩T｜＝3，｜X1｜≥6，则｜S∩C｜≥2。既然｜S｜＝5，又因为D∩S≠Ø，｜S∩T｜＝1，所以｜S∩C｜＝2或3，

若｜S∩C｜＝2，｜S∩D｜＝2，则｜X3｜＝｜X4｜＝4，故B∩C＝Ø＝B∩D，所以｜B｜＝｜B∩T｜＝1，设B＝B∩T＝｛t2｝，d（t2）＝5，且t2xixi＋1t2是3-圈，矛盾。

若｜S∩C｜＝3，｜S∩D｜＝1，则｜X2｜＝5，由A是E0-端片可知，A∩D＝Ø。故｜D｜＝｜S∩D｜＝1，设D＝S∩D＝｛t3｝，d（t3）＝5，且t3uv1t3是3-圈，矛盾。

（1.2）若｜B∩T｜＝2，D∩S≠Ø，则｜S∩T｜＝1。此时｜A∩T｜＝2，｜S∩D｜＝1，则｜X2｜＝4，A∩D＝Ø，得｜D｜＝｜S∩D｜＝1，设D＝S∩D＝｛t4｝，d（t4）＝5，且t4uv1t4是3-圈，矛盾。

（2）如果B∩T＝Ø，则B＝B∩C≠Ø，｜X4｜≥5，｜S｜＝5，所以S∩D＝Ø，矛盾。

由此可知，A∩C＝Ø。

由对称性，A∩D＝Ø＝A∩C。此时A＝A∩T≠Ø。A中不能只含有一个元素，否则有3-圈包含它，又因G无2-断片，故｜A｜＝｜A∩T｜≥3。又u∈S∩T，故｜B∩T｜＝0或1。

若｜B∩T｜＝0。u∈S∩T，｜S∩T｜≥1，由｜S｜＝｜T｜＝5可知，总有｜X3｜≤4或｜X4｜≤4成立，故B∩C＝Ø或B∩D＝Ø。由对称性不妨设B∩D＝Ø，则B＝B∩C≠Ø，｜X4｜≥5，｜S｜＝5，故｜X4｜＝5。此时D∩S＝Ø，又B∩D＝Ø，故D＝Ø，矛盾。

若｜B∩T｜＝1。由｜T｜＝5，｜A∩T｜≥3，u∈S∩T，则｜S∩T｜＝1，又｜S｜＝5，由S∩C和S∩D的对称性，只需讨论｜S∩C｜＝2或1，

若｜S∩C｜＝2，则｜S∩D｜＝2，所以｜X3｜＝｜X4｜＝4，故B∩C＝Ø＝B∩D，所以｜B｜＝｜B∩T｜＝1，设B＝B∩T＝｛t5｝，d（t5）＝5，且t5xixi＋1t5是3-圈，矛盾。

若｜S∩C｜＝1，则｜X4｜＝3，所以B∩C＝Ø，又因为A∩C＝Ø，所以｜C｜＝｜S∩C｜＝1，设C＝S∩C＝｛t6｝，d（t6）＝5，且t6v1ut6是3-圈，矛盾。

根据以上讨论可知P至少包含两条可收缩边，即原命题成立。证毕。

定理1 设G是5-连通图且G不包含2-断片。C：x＝x1x2…xn＝y是G的任意最长圈。若圈C上任一顶点xi都满足以下条件之一，则C至少包含三条可收缩边：

（1）d（xi）≥6；

（2）d（xi）＝5，则［V（C）］中无3-圈包含它。

证明：设x′y′是圈C上的一条边，显然P＝C－x′y′是G中一条最长（x′，y′）-路。由引理3可知，P至少包含两条可收缩边，设为u1v1和u2v2，则P′＝C－u1v1是G中一条最长（u1，v1）-路，由引理3可知，P′包含两条可收缩边，至少有一条u3v3≠u2v2，故C上至少有三条可收缩边。证毕。

［1］BONDY JA，MURTY U SR.Graph theory with applications［M］.London：The Macmillan Press Ltd，1976.

［2］TUTTEW T.A theory of 3-connected graphs［J］.Indag Math，1961，23：441－455.

［3］THOMASSEN C. Planarity and duality of finite and infinite graphs［J］.J Combin Theory Ser B，1980，29（2）：244－271.

［4］KRISELL M. A survey on contractible edges in graph of a prescribed vertex connectivity［J］.Graphs and Combinatorics，2002，18（1）：1－30.

［5］杨朝霞.某些5-连通图中最长圈上的可收缩边［J］.山东大学学报：理学版，2008，43（6）：12－14.

Distribution of contractible edges of some 5-connected graphs

WANG Zhen-gang，QI En-feng
（School of Mathematics，Shandong University，Jinan 250100，China））

Contractible edge issue plays an important role in the research on graph structure and the proof of some graph properties．We present the distribution of the contrac tible edges in some longest cycles of 5-connec tedg raphs and address their classification with tree struc ture theory．Our conclusion is that at least three contrac tible edges exist on some longest cycles of 5-connec tedg raphs．

5-connected；contrac tible edge；the longest cycle

O157.5

A

1002-4026（2014）05-0103-03

10.3976／j.issn.1002－4026.2014.05.019

2014-06-01

王振刚（1989－），男，硕士研究生，研究方向为图论。Email：zhengangok＠qq.com