Let G be a 4-connected graph. For an edge e of G, we do the following operations on G: first, delete the edge e from G, resulting the graph G - e; second, for all the vertices x of degree 3 in G - e, delete x from G - e and then completely connect the 3 neighbors of x by a triangle. If multiple edges occur, we use single edges to replace them. The final resultant graph is denoted by G-e. If G-e is still 4-connected, then e is called a removable edge of G. In this paper we prove that every 4-connected graph of order at least six (excluding the 2-cyclic graph of order six) has at least (4G + 16)/7 removable edges. We also give the structural characterization of 4-connected graphs for which the lower bound is sharp. (C) 2004 Elsevier Inc. All rights reserved.
展开▼
机译：令G为4连通图。对于G的边e，我们对G进行以下操作：首先，从G删除边e，得到图G-e;其次，对于G-e中所有3度的顶点x，从G-e中删除x，然后用一个三角形完全连接x的3个邻居。如果出现多个边缘，我们将使用单个边缘来替换它们。最终的结果图用G-e表示。如果Ge仍然是4连接的，则e称为G的可移动边。在本文中，我们证明至少4阶的每个4连通图（不包括6阶的2环图）至少具有（4 G + 16）/ 7个可移动边缘。我们还给出了下界很尖锐的4连通图的结构特征。 （C）2004 Elsevier Inc.保留所有权利。
展开▼
