Contractible Edges in a k-Connected Graph

Kiyoshi Ando
Department of Information and Communication Engineering,
The University of Electro -Communications, 1-5-1 Chofugaoka, Chofu City, Tokyo, 182-8585,

An edge of a k-connected graph G is said to be contractible if the contraction of the edge results in a k-connected graph. If an edge is not contractible, then it is said to be noncontractible. We denote the set of noncontractible edges of G by En(G). If E(G)=En(G), then G is said to be contraction critically k-connected.

Tutte proved that every 3-connected graph of order 5 or more contains a 3-contractible edge. Fonted and Martinov proved that a graph G is contraction critically 4-connected if and only if G is 4-connected, 4-regular and for each edge e of it there is a triangle containing e.

Thomassen proved that every k-connected triangle-free graph has a k-contractible edge. Further, Egawa, Enomoto and Saito showed that each k-connected triangle-free graph contains min{|V(G)| + (3/2) k2-3k, |E(G)|} k-contractible edges. Hence, a triangle-free graph has many contractible edges.

This situation indicates the possibility of the existence of a weaker forbidden subgraph condition for a k-connected graph to have a k-contractible edge. In this direction the following results are known. Let K4- stand for K2+2K1. We call K1+2K2 a bowtie. Let Vk(G) denote the set of vertices of degree k.

Theorem 1.1(Kawarabayashi) Let k 3 be an odd integer. Then every k-connected K4--free graph has a k-contractible edge.

Theorem 1.2(Ando, Kaneko, Kawarabayashi, Yoshimoto) Every k-connected bowtie-free graph has a k-contractible edge.

Theorem 1.3(Ando, Kaneko, Kawarabayashi) Every k-connected k\ge 5 (K1+P4)-free graph has a k-contractible edge, if G[Vk(G)] is bowtie-free.

Theorem 1.4(Ando, Kawarabayashi) Every k-connected k 5) {K2+sK1, K1+tK2}-free graph has a k-contractible edge, where k, s and t are positive integers such that s(t-1)< k.

By the result of Fontet and Martinov, we know that if a 4-connected graph G has a vertex whose degree is greater than 4, then G has a contractible edge. Hence, it seems to be natural to expect that there is a contractible edge near each vertex with degree greater than 4 in a 4-connected graph. In this direction the following results are known.

Theorem 1.5 [2]. Let G be a 4-connected graph with V(G)-V4(G) and let u V(G)-V4(G). Then there exists a 4-contractible edge e such that either e is incident with u, or at least one of the end vertices of e is adjacent to u. Further if G[NG(u) V4(G)] is not a path of order 4, then there are two such 4-contractible edges.

By virtue of Theorem \ref{e}, we get the following.

Theorem 1.6 [2]. Every 4-connected graph G has |V(G)|-|V4(G)| 4-contractible edges.

Let Edge(2)(x) denote the set of edges whose distance from x is 2 or less. 2K2+K1 is called an x*-bowtie if its vertex of degree 4 is x, and in each triangle of it, there is a vertex other than x whose degree is 5. K4- is called a reduced x*-bowtie if one of the vertices of degree 3 of it is x, and it has at least two vertices of degree 5 other than x. Let S={a1, a2, x, b1, b2} be a 5-cutset of a 5-connected graph G and let A be a component of G-S such that V(A) V5(G), |V(A)|=4 and G[A] K4-, sayA={ u1, u2, v1, v2 }, with edges within A and between A and S exactly as in Fig. 1; there may be edges between vertices of S. We call this configuration, G[V(A) S], a K4--configuration with center x.

Investigating the local structure around a vertex of 5-connected graph near which there are no contractible edges, we get the following local structure theorem of 5-connected graphs.
Theorem 1.7.Let x be a vertex of 5-connected graph G such that Edge(2)(x) En(G). If G has neither an x*-bowtie nor a reduced x*-bowtie, then G has a K4--configuration with center x.

As a consequence of Theorem 1.7, we prove the following, which is an improvement of the previous result in [1].

Theorem 1.8. Each contraction critically 5-connected graph of order n has at least (2n)/5 vertices of degree 5.

1. K. Ando, Trivially noncontractible edges in a contraction critically 5-connected graph, Disc. Math. 293(1-3) (2005) 61--72.
2. K. Ando, Yoshimi Egawa,Contractible edges in a 4-connected graph with vertices of greater than 4, preprint.