恰有k条非基本边的极小3连通图

设G是简单3连通图．G\e(删除边e)和G/e(收缩边e)都不是简单3连通图,则e称为G的基本边．对于3连通图中的非基本边．Tutte证明了：唯一没有非基本边的简单3连通图是轮．Oxley和Wu确定了至多有3条非基本边的所有极小3连通图以及恰有4条非基本的极小3连通图．Reid与Wu确定了至多有5条非基本边的极小3连通图．在本文中,我们在极小3连通图中定义了三种运算,然后通过轮利用这些运算的逆运算给出恰有k(k■2)条非基本边的极小3连通图的一种构造方法．

Minimally 3-Connected Graphs with Exactly k Non-Essential Edges

Let $G$ be a simple 3-connected graph. An edge $e$ of a simple 3-connected graph $G$ is essential if neither the deletion $G\backslash e$ nor the contraction $G/e$ is simple and 3-connected. For essential edges of a 3-connected graph, Tutte obtained the following theorem.\\8pt]{\bf Theorem 1}\ \ {\sl Let $G$ be a simple 3-connected graph. Then every edge is essential if and only if $G$ is a wheel.} This theorem ensures the existence of at least one non-essential edge in every simple 3-connected graph that is not a wheel. The existence of non-essential edges has become a powerful induction tool. Oxley and Wu proved that if $G$ is a minimally 3-connected graph that is not a wheel, then there are at least three non-essential edges, and characterized the minimally 3-connected graphs with exactly three non-essential edges. Reid and Wu also determined all minimally 3-connected graphs with at most five non-essential edges. In this paper, we use a quite different way to solve this problem. We prove the result by constructing all of the minimally 3-connected graphs with exactly $k$ non-essential edges through several operations, starting with a wheel. That is, firstly, in a minimally 3-connected graph, we define the following three operations: {\bf Operation One}: Deletion of any deletable vertex. {\bf Operation Two}: If the hub of a non-trivial fan is incident to only one edge out of the fan, then all the inner-vertices of the fan and the hub of the non-trivial fan are contracted into a vertex. If the vertex is a deletable vertex, then it is deleted. {\bf Operation Three}: If the hub of a non-trivial fan is incident to two or more edges out of the fan, then the non-trivial fan is transformed into a triad (that is, in the non-trivial fan, we contract all arcs and delete loops and multi-edges). First, if the three edges of the triad are simple-contractible, the simple-contractible edge that is incident to the hub of the former non-trivial fan is contracted. All the generated deletable edges are deleted in turn, till there are no deletable edges in the graph. Secondly, if there are exactly two simple-contractible edges in the triad, then any one of them is contracted, and all the generated deletable edges are deleted in turn, till there are no deletable edges in the graph. For any non-trivial fan. Operation One is applied on any one of contractible edges chosen from the fan. Then by the above operations and the operation of adding edges, we can construct all minimally 3-connected graphs with exactly $k~(k\geq{3})$ non-essential edges, starting with a wheel. By induction, a minimally 3-connected graph with exactly $k~(k\geq{4})$ non-essential edges, can be transformed into a minimally 3-connected graph with much less non-essential edges by a series of these operations. According to the induction hypothesis, a minimally 3-connected graph with less than $k$ non-essential edges can be obtained from a wheel by the inverse of the used operations. Therefore, a minimally 3-connected graph with exactly $k$ non-essential edges can be obtained from a wheel by the inverse of the used operations. In this way, all minimally 3-connected graphs with exactly $k$ non-essential edges can be constructed completely. So, we obtain the following main result of the paper: \\8pt]{\bf Theorem 2}\ \ {\sl $G_{k}~(k\geq{3})$ can be transformed into $W$ through a series of Operation One, Two, Three and the deletion of edges. Hence, $G_{k}~(k\geq{3})$ can be obtained from a wheel by the inverse of the used operations, where $G_{k}$ and $W$ are used to denote a minimally 3-connected graph with exactly $k$ non-essential edges and a wheel, respectively.