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 *E*_{n}(G). If
*E(G)=E*_{n}(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) k^{2}-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 *K*_{4}^{-} stand for *K*_{2}+2K_{1}. We
call *K*_{1}+2K_{2} a *bowtie*. Let *V*_{k}(G) denote the set of
vertices of degree *k*.

**Theorem 1.1(Kawarabayashi)** Let *k 3* be an odd
integer. Then every *k*-connected *K*_{4}^{-}-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* *(K*_{1}+P_{4})-free graph has a
*k*-contractible edge, if *G[V*_{k}(G)] is bowtie-free.

**Theorem 1.4(Ando, Kawarabayashi)**
Every *k*-connected *k 5*) {K_{2}+sK_{1},
K_{1}+tK_{2}}-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)-V*_{4}(G) and let *u V(G)-V*_{4}(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[N*_{G(u)} V_{4}(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)|-|V*_{4}(G)| *4*-contractible edges.

Let *Edge*^{(2)}(x) denote the set of edges whose distance from
*x* is 2 or less. *2K*_{2}+K_{1} 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. *K*_{4}^{-} 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={a*_{1}, a_{2}, x, b_{1}, b_{2}} be a
5-cutset of a 5-connected graph *G* and let *A* be a component
of *G-S* such that *V(A) V*_{5}(G),
*|V(A)|=4* and *G[A] K*_{4}^{-}, sayA={ * u*_{1}, u_{2}, v_{1}, v_{2} },
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 *K*_{4}^{-}-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) E_{n}(G). If *G* has
neither an *x**-bowtie nor a reduced *x**-bowtie, then *G* has a
*K*_{4}^{-}-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.