论文摘要
如果将k连通图G中的一条边收缩之后所得到的图仍然k连通，则称这条边为G的k可收缩边。利用阶至少是5的3连通图中存在3可收缩边这一性质，1980年Thomassen（[1]）使用归纳法统一证明了关于平面图的Kuratowski等三个重要定理。自那以来，人们对k连通图中k可收缩边进行了大量的研究（[2][3][4][5]）。不存在k可收缩边的非完全k连通图称为收缩临界k连通图。由于收缩临界k连通图每一个性质的否定都可得到k连通图中存在k可收缩边的充分条件，因而对k连通图中k可收缩边进行研究就转化为对收缩临界k连通图性质的研究。最先Egawa（[6]）证明每一个收缩临界k连通图有一个基数小于等于k／4的断片，由此可推出当k=4，5，6，7时，收缩临界k连通图的最小度等于k。已经知道不存在收缩临界3连通图（[7]），收缩临界4连通图的结构已经完全清楚，它们是两类特殊的4正则图（[8][9]），接着自然要想弄清收缩临界5连通图的结构，经过多年的探索，人们发现这是一个十分困难的问题。为了弄清收缩临界5连通图的结构，首先要了解收缩临界5连通图性质。由前面Egawa的结果知道收缩临界5连通图至少有一个5度顶点，对于收缩临界5连通图中5度顶点的分布，袁旭东在1994年得到：定理A（[10]）收缩临界5连通图中每一个点都与1个5度点相邻。由此可以推出G中至少有1／5|G|个5度顶点。1997年苏健基进一步证明了：定理B（[11]）收缩临界5连通图中每一个点都与2个5度点相邻。由此可以推出G中至少有2／5|G|个5度顶点。到了2003年，Ando又重复得到袁在1994年得到的结果。对于收缩临界5连通图G中5度顶点数的下界，最近覃城阜改进到：定理C（[12]）设G是收缩临界5连通图，则G至少有4／9|G|个5度顶点。本文进一步得到：定理1若G为收缩临界5连通图，则G中至少有1／2|G|个5度顶点。对于收缩临界k连通图G，最早Thomassen（[1]）证明图中都有三边形，后来Mader（[13]）改进到有|G|／3个三边形，最近Kriesell（[14]）证明至少有2|G|／3个三边形。由于收缩临界5连通图中有很多三边形，又有很多5度顶点，因而也会有不少通过5度顶点的三边形。如果k连通图的一条边在三边形上，并且它所对的顶点是k度顶点，也即这条边的两个端点有一个公共邻点是k度点，这条边显然是不可收缩边，称为平凡不可收缩边。Ando研究了收缩临界5连通图中平凡不可收缩边的分布，证明了：定理D（[15]）收缩临界5连通图G至少有1／2|G|条平凡不可收缩边。他还提出猜想：猜想收缩临界5连通图G至少有2|G|条平凡不可收缩边。最近李向军证明了：定理E（[16]）收缩临界5连通图G至少有|G|+1条平凡不可收缩边。本文在此基础上进一步得到：定理2若G为收缩临界5连通图，则G中至少有3／2|G|条平凡不可收缩边。