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,
Japan
Abstract
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.
References
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.
