Admissible vertices of contraction-critically 5-connected graphs
Kiyoshi Ando
abstract
Let G be a 5-connected graph. An edge of a G is said to be 5-contractible if the contraction of
the edge results in a 5-connected graph. If G has no 5-contractible edge, then it is said to becontraction-critical. An induced subgraph A of G is said to be a fragment if, wherevertexandis the neighborhood of A. For a fragment A andis said to be an admissible vertex for, if the degree of, ais 5 and. We show some new properties on admissible vertices of contraction-critically
5-connected graphs. Using admissible vertices, we give a result on the structure around a fragment
whose cardinality is 2.
Key Words: 5-connected graph, contraction-critically 5-connected, degree 5 vertex AMS
classification: 05C40
Dedicated to Professor Hideo Osawa on the occasion of his retirement.
1 Introduction
In this paper, we deal with finite undirected graphs with neither self-loop nor multiple edge.
For a graph G, letandrespectively. We calldenote the set of vertices of G and the set of edges of G,andthe order of G and the size of G, respectively. Let

denote the set of vertices of degree k. For an edgeby. For a vertex

subset, we denote by, leta vertex, we denote the set of end vertices of
the neighborhood of. We denote the degree of, we denote by

,

,

,

by

. For

the set of edges incident with. When there is no ambiguity, we writeforin G. Moreover, for aanddenote the subgraph induced by S in G. For, respectively. For, we let− 11 −,,. Then,and, we letdenote the graph obtained

RESEARCH BULLETIN

from G by deleting the vertices in S=

. A subset

No.86

together with the edges incident with them; thus

is said to be a cutset of G, if

is said to be a k-cutset if

is not connected. A cutset S. For a noncomplete connected graph G, the order of a minimum

cutset of G is said to be the connectivity of G denoted by. We denote by. Let G be a connected graph withthe complete graph on n vertices. For graphs G and H, we write

the join of G and H.
Let k be an integer such thatand let G be a k-connected graph with.

An edge e of G is said to be k-contractible if the contraction of the edge results in a k-connected
graph. Note that, in the contraction, we replace each resulting pair of double edges by a simple edge.
If an edge is not k-contractible, then it is called k-noncontractible. Note that an edge e of G is
k-noncontractible if and only if there is a k-cutset S of G such that

. If G does not have ak-contractible edge, then G is said to be contraction-critically k-connected.
An induced subgraph A of G is called a fragment if
If

and

.

, then a fragment A is called i-fragment. A noncontractible edge e is said to be trivial, if

there is a fragment A such thatand

. A noncontractible edge e is said to be far

from trivial, if | A | 12 (| V (G ) | 2k ) for any fragment A such that
Let G be a 5-connected graph. Let
. For

.

and let A be a fragment of G such that

, a vertex z is said to be an admissible vertex for
and

, if

. A vertex z is said to be an admissible vertex for, if z is an admissible vertex for ( x , y; A) for some y  N ( x )  A .
It is known that every 3-connected graph of order 5 or more contains a 3-contractible edge[13]. There are infinitely many contraction-critically k-connected graphs for each[12]. It is

known that a 4-connected graph G is contarction-critical if and only if G is 4-regular, and for eachedge e of it, there is a triangle which contains e [8, 10].
Egawa determined the following sharp minimum degree condition for a k-connected graph tohave a k-contractible edge.
Theorem A (Egawa [7])Let k be an integer, let G be a k-connected graph with

Then G has a k-contractible edge, unless

and G is isomorphic to.

.

There are infinitely many contraction-critically 5-connected graphs which are not 5-regular.
However, by virtue of Theorem A, we know that the minimum degree of a contraction-critically
5-connected graph is 5.
The following result due to Su says that there are degree 5 vertices everywhere in a
− 12 −

Admissible vertices of contraction-critically 5-connected graphs

contraction-critically 5-connected graph.
Theorem B (Su [11])Every vertex of a contraction-critically 5-connected graph has twoneighbors of degree five.
Since a contraction-critically 4-connected graph is 4-regular, it has very restricted
substructure. On the other hand, for any given graph, there is a contraction-critically 5-connected
graph which has it as an induced subgraph.
Theorem C (Ando and Kawarabayashi [6])Let k be an integer such thatand let H be agraph. Then, we can construct a contraction-critically k-connected graph which contains H as an
induced subgraph.
Theorem C indicates the big difference between ‘contraction-critically 4-connected graphsʼ and‘contraction-critically 5-connected graphsʼ. As Kriesell wrote in [9], it is probably a tremendously hard
problem to characterize contraction-critically k-connected graphs for. Although we still do nothave enough knowledge of the global structure of contraction-critically 5-connected graphs, we havea local structure theorem on contraction-critically 5-connected graphs [1] and we also have some
progress on the study of contraction-critically 5-connected graphs [3, 4, 5, 6]. In the last decade, in the
study of contraction-critically 5-connected graphs, ‘admissible verticesʼ play crucial roles. In thispaper we focus on admissible vertices of contraction-critically 5-connected graphs and we show somenew conditions for a contraction-critically 5-connected graph to have an admissible vertex.
Furthermore, using admissible vertices, we prove the following Theorem 1 which shows theremarkable structure around a connected 2-fragment of a contraction-critically 5-connected graph.
Theorem 1
fragment of G with
(1) If

Let G be a contraction-critically 5-connected graph. Let A be a connected, sayand let, then the number of vertices.
such that there is an admissible vertex foris greater than or equal to 4.
(2) If, then the number of admissible vertices for someis greater than orequal to 3.
(3) Ifvertex for, then there is a vertex

such that there is an admissible.

− 13 −RESEARCH BULLETIN

No.86

This paper consists of 4 sections. After presenting preliminary results in section 2, we givesome sufficient conditions for the existence of admissible vertices for given pair

, where A is a

fragment of a contraction-critically 5-connected graph and x  N ( A) , in section 3. In section 4, wegive a proof of Theorem 1.
To conclude the section, we present three contraction-critically 5-connected graphs. The firstone is 5-regular, and for each edge e of it, there is a triangle which contains e. Hence, this graph issimilar in structure to contraction-critically 4-connected graphs. The second one has large maximum
degree. The last one has an edge which is far from trivial. We observe that every edge in acontraction-critically 4-connected graph is trivial and, every edge of the first example and the second
example is trivial. However the number of non-trivial noncontractible edges of the last example is
proportional to the size of it.
Example 1
Identifying the top and the bottom, and the left side and the right side of the graph in Fig 1,
we obtain a 5-regular contraction-critically 5-connected graph for each edge e of which, there is atriangle containing e.

Fig.1: A contraction-critically 5-connected graph similar in structure to contraction contractioncritically 4-connected graphs
Example 2
Let H be a contraction-critically 4-connected graph and let. Then, we observethat G is 5-connected and every edge of G is trivially 5-noncontractible. Hence G is a contraction-− 14 −

Admissible vertices of contraction-critically 5-connected graphs

critically 5-connected graph with.

Example 3
stand for the graph obtained fromLet

Let m be an integer such that
configuration

and we constructwhich consists of m copies ofvertices and join them to bottom part vertices ofto the left side 2 vertices ofright side 2 vertices ofby removing one edge; that is K 4   K 2  2 K 1 .
as follows; At first we prepare a（see in Fig.2）. Next take other three distinct. At last take two distinct

ʼs and join one

and the three distinct vertices, and join the otherto theand the three distinct vertices, appropriately（see Fig.3）.

Fig.2:
We call the resulting graphthat there is a 5-cutset of

consisting ofobserve that this is the only 5-cutset inthat. Let e be an edge of the top part of. Then we observeand the distinct three vertices. Moreover, we

which contains V ( e ) . By these observations, we know

is a contraction-critically 5-connected graph and it has a far from trivial edge and many

non-trivial 5-noncontractible edges.

Fig.3:: contraction-critically 5-connected graph with many non-trivial edges− 15 −RESEARCH BULLETIN

No.86

2 Preliminaries
In this section we give some more definitions and preliminary results.
For a graph G, we denotefor. For a subgraphs A and B of a graph G, when there

is no ambiguity, we write simply A forandand B for

. So

and

mean

, respectively. Also for a subgraph A of G and a subset S of

and

for

for

and

we write, respectively. When there is no ambiguity, we write. For subset S and T of V (G ) , we denote the set of edges between S and T by
. We write
for

for

. When there is no ambiguity, we writeand, respectively. Let（or sometimes simply

and）denotethe set of vertices of degree at least k.
Let G be a connected graph withfragment if. Recall that an induced subgraph A of G is called aandunion of components of. In other words, a fragment A is a nonempty
where S is a k-cutset of G such thatdefinition, if A is a fragment of G, then

. By theis also a fragment of G. Let

stand for. For an edge e of G, a fragment A of G is said to be a fragment with respect to e if
. For a set of edges, we say that A is a fragment with respect to F if A is a

fragment with respect to some

. A fragment A with respect to F is said to be minimum（resp.

minimal） if there is no fragment B other than A with respect to F such that）
. If

, then a fragment A is said to be trivial.

Let（or sometimes simply

has i neighbors in Vk (G ) , namely V(i)k）stand for the set of vertices of（resp.
each of which {x  Vk (G ) | | N ( x )  Vk (G ) | i} .

We start with the following Lemma 1 [3] which is a simple but useful observation. We give a
proof of Lemma 1 for the readerʼs convenience.
Lemma 1 Let A be a fragment of a k-connected graph G and let

. If

,

. Since

and

.

then

Assume that

Proof.
,. Let
separates

that

and

. Since, we see, which contradicts thek-connectedness of G.

▋

The reader can find the proof of Lemma 2 in [3].

− 16 −

If |N (S) ∩ A| < |S|, then A = N (S) ∩ A.
Proof. Assume that A ̸= N (S) ∩ A. Let A′ = A − (N (S) ∩ A). Since A′ ̸= ∅ andT ∩(Ā∪S) = ∅, (N (A)−S)∪(N (S)∩A) separates A′ and Ā∪S. Since |N (S)∩A| < |S|,
we see that |(N (A) − S) ∪ (N (S) ∩ A) = |N (A)| − |S| + |N (S) ∩ A| < |N (A)| = k,vertices of contraction-critically 5-connected graphs
which contradictsAdmissible
the k-connectednessof G.
The reader can find the proof of Lemma 2 in [3].

Lemma 2 Let G be a 5-connected graph, and let A and B be fragments of G. Let
let

and

.
Lemma
2
Let G be a 5-connected graph, and let A and B be fragments of G.
Let S = N (A) and let T = N (B).

BĀ ∩ B

S∩B

A∩B

T

Ā ∩ T

S∩T

A∩T

B̄

Ā ∩ B̄S ∩ B̄

A ∩ B̄

Ā

S

A

Then
thethefollowinghold. hold. (1) If |(S ∩ B) ∪ (S ∩ T ) ∪ (A ∩ T )| ≥ 6, then |(Ā ∩ T ) ∪Thenfollowing(1) If, thenIn particular, if neither

and6 bothis empty, then

nor

(2)

and

.

are fragments of G.

. In particular, if, then.
(3) If, then eitheror.
3 Admissible vertices
In the following two sections we consider 5-connected graphs.
We introduce ‘admissible vertexʼ in [3] and we introduce ‘strongly admissible vertexʼ and‘hyper admissible vertexʼ in [2]. In this paper, we introduce ‘insufficient’ and give a new sufficientcondition a contraction-critically 5-connected graph to have an admissible vertex.
Let G be a 5-connected graph. Let
. Let
Let

and let A be a fragment of G such that.
. Recall that a vertex z is said to be an admissible vertex for, if thefollowing two conditions hold.
(1)
(2)

.
.

Here, we introduce more detailed properties of admissible vertices.
For, a vertex z is said to be an strongly admissible vertex for

following conditions hold.

− 17 −, if theRESEARCH BULLETIN

(1)

No.86

,

(2)

, and

(3)

.

For

, a vertex z is said to be an hyper admissible vertex for, if thefollowing conditions hold.
(1)

,

(2)

, and

(3)

.

A vertex z is said to be a strongly admissible vertex for, if z is a strongly admissible vertex forforfor someor a hyper admissible vertex

or a hyper admissible vertex for, respectively.

A triangle H of G is said to be an A-innerand (3)-triangle if (1)

, (2)

.

A vertex x is said to be insufficient on A if the following two conditions hold.
(1) there is no A-inner-triangle.

(2)

for any.

The following Lemmas 3 and 4 give some basic properties of admissible vertices in acontraction-critically 5-connected graph. The reader can find proofs of Lemmas 3 and 4, andCorollary 7 in [3], however for the convenience of the reader, we give proofs of Lemmas 3 and 4. We
give an alternate proof of Corollary 7 in this section.
Lemma 3 ([3] Corollary 4)

Let x be a vertex of a contraction-critically 5-connected graph G.

Let A be a fragment of G such that. Suppose,and. Then,there is an admissible vertex for. Let B be a fragment with respect to xy. Let

Let

Proof.

. Since, by Lemma 2 (3), we see that either

and letor. Without loss of generality we may assume. Then, since, we have

Claim 3.1
Proof.
we assume.

.
If, then. Then, since, we have− 18 −

since. Hence,and, whichAdmissible vertices of contraction-critically 5-connected graphs

implies that

since

.

Hence we observe thatand Claim 3.1 is proved.
. If

Claim 3.1 assures us that▋, thenand, which contradicts the fact thatHence

. Claim 3.1 also assures us that

andThen we observe that z is an admissible vertex forLemma 4 ([3] Lemma 3)

.

.

. Let

.

▋

Let x be a vertex of a contraction-critically 5-connected graph G.
,

Let A be a fragment such that

andthere is either an admissible vertex for. Then, for each vertex

or a fragment,with respect to xy such that.
Assume that there is neither an admissible vertex for

Proof.

with respect to xy such that
. Since

nor a fragment. Let B be a fragment with respect to xy. Let

and let, by Lemma 2 (3), we see that eitheror. Without loss of generality we may assume. If, thenis a fragment with respect to xy such that, which contradicts the assumption. Hence
Claim 4.1▋.
AssumeProof.

.

. Thenand. Hence. ThusThen, we find that z is an admissible vertex for
By Claim 4.1, we know that

. Hence, if

Thus we have
Therefore,

, say

.

, which contradicts the assumption.

a fragment with respect to xy such that, then, which contradicts the assumption.

, which implies

and

.

and

. Hence we haveadmissible vertex forLemma 4.

since

, say

. Then, we again find that z is an, which contradicts the assumption. This contradiction proves▋

Lemma 5 Let x be a vertex of a contraction-critically 5-connected graph G. Let A be asuch that,. If there is neither an A-inner-triangle
fragment with respect tonor an admissible vertex for, then,.

− 19 −RESEARCH BULLETIN

Let

Proof.

and assume that either

S  N ( A)  {x , w, w, w, w} . We may assume

also assume that.

Claim 5.1S  {x}  N ( u) .

Proof.

Ifor

and we are done. Hence assume. If-triangle, which violates the assumption.

, which implies the desired conclusion,(1)

Proof.

(1) By Claim 5.1, we see that.
, which implies. Thensince

we seeand let, we have, then▋.

.

Assume thatand

. Then, by Claim 5.1, we see that.

, which contradicts the assumption.

.

Claim 5.4
us that. Similarly

andThis implies w is an admissible vertex for

Proof.

,. Then we see that.

By Claim 5.2 (2), we may assume that

Proof.

, then, which contradicts the assumption. Hence. Then, since

Claim 5.3 If

.

. If

which contradicts the choice of B. Hence assume
y is an admissible vertex for▋.

and (2)(2) Assume.

and letClaim 5.2

S  N ( A)  {x , w, w, w, weis an A-inner

Let B be a fragment with respect to. Let. Since A is a fragment with respect to, then, then we see that
Hence

No.86

Assume. Then. Hence. By Claim 5.1, we know thatand let. Then, since

and Claim 4.3 assures. Let C be a fragment with respect to, we see that, which implies.

▋
Subclaim 5.4.1
Proof.
since
which implies

Assume.
. Without loss of generality we may assume that

, we observe that

. Sincesince

we see that. Now we observe that− 20 −. Then,,andAdmissible vertices of contraction-critically 5-connected graphs, which implies thatfragment of G. Since,. Henceand, we see that

Hence, applying Lemma 1 with the roles of A and S replaced bysee that. This implies

Subclaim 5.4.1.

.
and, which contradicts Claim 5.3. This contradiction proves(1), and (2).

(1) By Subclaim 5.4.1, we know thator

, which implies either. Without loss of generality we may assume that

. Then. Since, which implies, we see that
(2) Since

and

, say

, Lemma 2 (2) assures us that

. Henceand. Since.

, we observe that

.

▋

.

Subclaim 5.4.3
Since

Proof.

, respectively, we▋

Subclaim 5.4.2
Proof.

is a, we see that
. Sinceand, which implies, we observe that
. Since, we see that
, we have

. Let
and

, which implies.

. Sinceand▋We proceed with the proof of Claim 5.4. Now we observe that, whichimplies xv is contractible. This contradicts that G is contraction-critically 5-connected and Claim 5.4 isproved.

▋By Claim 5.4, we haveis an A-inner. Hence. But, in this situation, we see that-triangle, which contradicts the assumption. This contradiction proves Lemma 5. ▋Recall that an vertex x is said to be insuﬃcient on a fragment A if (1) there is no A-inner-triangle and (2)for any.

The following Lemma 6 says that ̀̀x is insuﬃcient on A" is an suﬃcient condition for the
existence of an admissible vertex for.

Lemma 6 Let x be a vertex of a contraction-critically 5-connected graph G. Let A be a fragment− 21 −RESEARCH BULLETIN

such that
for

,

and

No.86

. If x is insufficient on A, then there is an admissible vertex.
We prove Lemma 6 by the induction on

Proof.

. If

3 assures us that the desired conclusion holds. Assume
no admissible vertex for. Chooseto be as small as possible.

, Lemma 5 assures us that there is a fragment.

.

Claim 6.1

At ﬁrst assume

Proof.

and also assume that there isso thatSince there is no admissible vertex forwith respect to xy such that, then Lemma, say. Then. In this situation, we observe that,is an A-innerand-triangle, which violates

the fact that x is insuﬃcient on A.
Next assume. Then, x is also insuﬃcient onand. Since x is insuﬃcient on A and. Sinceand, we see that

. Hence, applying the induction hypothesis toadmissible vertex z for. Since. Assume that,

, we see that there is an, which implies. Since z is an admissible vertex for. Then, sinceand. We show, there is a vertex, we observe thatis an-triangle, which violates the fact that x is insuﬃcient on A. Now it is shown that

A-innerwhich implies that z is an admissible vertex z for
6.1 is proved.

,. This contradicts the assumption and Claim▋

By Claim 6.1 we know

, sayand there is no A-innerthere is an admissible vertex z for
we ﬁnd an A-inner. We may assume that-triangle, we see there is no. Then-inner. Since-triangle. Assume that

and

. If

-triangle, which contradicts the assumption. Hence, thenand z is anadmissible vertex for, which again contradicts the assumption. It is shown that there is no

admissible vertex for. Hence, there is neither anvertex for-inner. Thus Lemma 4 assures us that

. Recall that we choose y so thatto be as small as possible. Hence, we see thatis no A-inner-triangle and

since

. If

contradicts the assumption. Hence-triangle nor an admissible

since. Since there, we see that, thenis an A-inner, which implies

and, which implies-triangle, which. Now we observe that, which contradicts the assumption that x is
− 22 −

Admissible vertices of contraction-critically 5-connected graphs

insuﬃcient on A. This contradiction completes the proof of Lemma 6.

▋

We note that, in the deﬁnition of ̀insuﬃcient', the condition (2)for any” is necessary. There is a contraction-critically 5-connected graph G

which has a vertex x and a fragment A such thatan admissible vertex fornor an A-inner

By the deﬁnition, if,

andand G has neither-triangle.

, then x is insuﬃcient on A. Hence, the following is animmediate corollary of Lemma 6.
Corollary 7 ([3] Lemma 6) Let G be a contraction-critically 5-connected graph G and let A be a
fragment of G withandadmissible vertex for

.

. Let

. If

, then there is an▋

Lemma 8 Let x be a vertex of a contraction-critically 5-connected graph G. Let A be a fragment
such that,and. Supposeand(1) there is a strongly admissible vertex z for(2) if. Then,,Proof.

Letand let. Note that

By Lemma 3, there is an admissible vertex z for

since

. Let

we see that,
. Since. Let

and let, we observe thatis a fragment of G such that

. Then, sinceand, which implies that there is no admissible vertex forthen Lemma 3 assures us the existence of an admissible vertex forprevious assertion. Hence we have

, say

. Since. Then. Let. Sinceandnoris trivial, and hence

andbe a fragment with respect to zu and letand− 23 −,. Without loss of, we see that

.

. If

and

, we see thatgenerality, we may assume that

, we observe, which contradicts the. Moreover we observe thatthat neither

,

and

and
that

.
. Then, sinceand. Furthermore, let.

and letWe show (1). Assume z is not strongly admissible, that is

that

.

, then z is a hyper admissible vertex for, which implies. Since, we seeRESEARCH BULLETIN.

Claim 8.1

AssumeProof.

No.86

since

. Without loss of generality, we may assume that,

. Then,. Hence, we observe that

. Then,assures us that, which contradicts the previous observation that
contradiction proves Claim 8.1.
▋
By Claim 8.1, we see thatsince

. This, which implies. We also observe that

. Since neither

since
nor

or

, we have either. Without loss of generality, we may assume that

, say

. Then we see that

applying Lemma 1 with the roles of A and S replaced byand, respectively, we see that, which contradicts the previous observation thatz is a strongly admissible vertex forand. This contradiction proves thatand (1) is shown.

Next we show (2). Assume z is not a hyper admissible vertex for. We show. Since z is strongly admissible and not hyper admissible, we see
that

,

,

,

and

and

. Let

. Thenand.

At ﬁrst we consider the case that

. In this case we have,

. Thus Lemma 3 assures us the existence of an admissible vertex for

Since

and

, we observe that w is an admissible vertex for

Next we consider the case that
, we see thatto zu and let

, say
and

, the fact

implies. Let. Since
and

nor
then

and

.

Claim 8.2 w is an admissible vertex forand,is a fragment of G such that

. Note that

Proof.

. Let. Sinceandbe a fragment with respect, which implies, we see that neither. We show that either, then we haveand

. Sinceoror, then, the fact that.

. Since, we observe that, which implies either. If. Hence assume

assures us that. Now it is shown that either− 24 −.

,. If. Similarly, ifor.

Admissible vertices of contraction-critically 5-connected graphs

Without loss of generality, we may assume that
, we observe that
and

, say
and

. Since. Hence we know thatand

, we see thatthe desired conclusion that w is an admissible vertex for
If. Then, since.

, then, which implies▋

and we are done. Hence assume.
Claim 8.3 If, thenAssumeProof.
observe.
. Since, which implies

Hence

.
, we see. This implies the desired conclusion▋.

Claim 8.4
AssumeProof.

, we. Then, since, which implies.

andis a fragment of G since

, say

that

,

. Then, sinceand. Hence Claim 8.3 assures us that

, we see that

. Sinceand, applying Corollary 7, we see that there is an admissible vertex for,and, we observe that, z is not an admissible vertex for
vertex for. Since. Since, which implies that there is no admissible. This contradicts the previous assertion and this contradiction proves Claim 8.4. ▋.

Claim 8.5
Since

Proof.
implies that,and

, we observe that, whichis a fragment of G since, which implies. This implies the desired conclusion that.

▋

We proceed with the proof of Lemma 8 (2).
Since

and

, applying Corollary 7, we see that there is anadmissible vertex

forwhich implies. Then, sincethat
we have. Since. Since, z is not an admissible vertex for, we observe that,, which implies
impliesand Claim 8.3 assures us that− 25 −,. Since. Now,

RESEARCH BULLETIN

and

No.86

, applying (1), we see that there is a strongly admissible vertex for.

However, since,strongly admissible vertex for, which violates the previous assertion. This contradiction

andproves (2) and the proof of Lemma 8 is completed.

, we see that there is no▋

4 The proof of Theorem 1
In this section we give a proof of Theorem 1.
Let G be a 5-connected graph. Let A be a fragment of G and let
denote the set of admissible vertices for（Y;A）. We demoteand let. Let Ad（Y;A）

the set of vertices y of S such that

. Using these notation, we can rewrite Theorem 1 as thefollowing.
Let G be a contraction-critically 5-connected graph. Let A be a connected

Theorem 1
fragment of G with, say

(1) If, then(2) If,(3) If, thenand let.

.
.
.

We prove Theorem 1 using the notation

and

. Let

of generality we may assume that

. Without loss

. Hence, if, thenand.
(1) Assume

and. ThenWe show that there is a fragment. If, then let

we observe thatLet.

such thatforbe a fragment with respect to. If. Then, sinceof a fragment, say, then let,

be a fragment with respect to, we again observe thatsuch that. Then, since. Let. Now the existence

is shown.

be a fragment such thatand letshow that. Suppose. Then, since

us that, which implies

, say

for

. We

, Lemma 2 (2) assures. Then we observeand, which implies that y is an admissible vertex forfact thatand it is shown that

. This contradicts the.

By the similar arguments, we can show that− 26 −. Thus we haveAdmissible vertices of contraction-critically 5-connected graphsfor. Without loss of generality we may assume that

and

. Say

Then we observe that
We showandand. Supposenor.
. Thenandis empty, we see that
and
and

and

. Hence, say

is a fragment of G. Since, respectively, we see that,andis empty, we see thatand S replaced by, applying Lemma 1 with the roles of A
and

and

, respectively, we see that

. HenceThis contradiction shows that, which implies, which again contradicts the choice ofand. Sinceand, we see that

, we see that, say

. Sincefor, we see thator

, which implies

and, we see that, which impliesand.

and (1) is proved.

(2) Assume,. Since neither

is a fragment of G. Since

and

say

. This contradiction.

noreither, which implies, which contradicts the choice ofIn this situation, we observe thatSince

. Since neither, applying Lemma 1 with the roles of A and S

replaced by
shows

.

, say

. Since.
and, we see that

. Since

for
and

,

.
By the same arguments in the proof of (1), we see there is a fragment B withand we also havemay assume that

. Let

. Sinceand, which implies
this contradiction shows. This contradicts (1) and. Now (2) is proved.
. Since, which implies

and, we observe that

, say
for

and

. Thenobserve thatand by the assumption, we. Sincebe a fragment with respect to
We show that. Suppose

we observe thatand it is shown that

, we
, we see thatand(3) Assume

Let. Since, we observe thatand let, say, which implies.
− 27 −

for

for

.

.

. Then since. This contradicts the choice of,RESEARCH BULLETIN

Similarly we haveNo.86

. Now we know thatand neither. Sincenor

nor

is empty, we see neither

is empty, which implies either
, say

or

and letWe show that. Suppose.

. Then, sinceLemma 1 with the roles of A and S replaced by, which implies, applying

and

and

, respectively, we see that

. Hence we havecontradicts the assumption that, which. This contradiction shows that

We show that. Suppose. Then, sinceLemma 1 with the roles of A and S replaced by, which implies.
, applying

and, respectively, we see that

. This contradicts the assumption thatand it is shown that.

By symmetry we have

. By the similar argument, we know that there is an integer

such that

and

and

.

We show. Supposenor. In this situation we observe that

. Thenand. Since neither

is empty, Lemma 2 (1) assures us that
andand S replaced by, applying Lemma 1, with the roles of A
and

and

, respectively, we see that

. Henceand it is shown that

Then

,

empty, we see thatis a fragment of G. Since, which, say, which implies

contradicts the assumption that.

and

. Since neither

is a fragment of G. Since, which implies, which contradicts the assumption that
that

is

and

, applying Lemma 1 with the roles of A and S replaced byrespectively, we see that

nor

and

and

,
. Hence. This contradiction shows. Now (3) is proved and the proof of Theorem 1 is completed. ▋Acknowledgements}
The author would like to thank Professor Yoshimi Egawa and Mr. Wei Tang for their detailed
and valuable comments.

− 28 −

Admissible vertices of contraction-critically 5-connected graphs

References[1] K. Ando, A local structure theorem on 5-connected graphs, J. Graph Theory 60 (2009), 99-129.
[2] K. Ando, Y. Egawa, and M. Kriesell The average degree of minimally contraction-critically 5-connected graphs, J.
Graph Theory 75 (2014), no. 4, 331-354.
[3] K. Ando and T. Iwase, The number of vertices of degree 5 in a contraction-critically 5-connected graph, Discrete
Math. 311 (2011), 1925-1939.
[4] K. Ando, A. Kaneko and K. Kawarabayashi, Vertices of degree 5 in a contraction critically 5-connected graphs,
Graphs Combin. 21 (2005), 27-37.
[5] K. Ando, A. Kaneko, K. Kawarabayashi and K. Yoshimoto, Contractible edges and bowties in a k-connected graph,
Ars Combin. 64 (2002), 239-247.
[6] K. Ando and K. Kawarabayashi, Some forbidden subgraph conditions for a graph to have a k-contractible edge,
Discrete Math. 267 (2003), 3-11.
, Graphs[7] Y. Egawa, Contractible edges in n-connected graphs with minimum degree greater that or equal to
Combin. 7 (1991), 15-21.
[8] M. Fontet, Graphes 4-essentiels, C. R. Acad. Sci. Paris 287 (1978), 289-290.
[9] M. Kriesell, A survey on contractible edges in graphs of a prescribed vertex connectivity, Graphs Combin. 18 (2002),
1-30.
[10] N. Martinov, Uncontractible 4-connected graphs, J. Graph Theory 6 (1982), 343-344.
[11] J. Su, Vertices of degree 5 in contraction critical 5-connected graphs, J. Guangxi Norm. Univ. 3 (1997), 12-16 (inChinese ).
[12] C. Thomassen, Non-separating cycles in k-connected graphs, J. Graph Theory 5 (1981), 351-354.
[13] W. T. Tutte, A theory of 3-connected graphs, Indag. Math. 23 (1961), 441--455.

− 29 −