How to Contract a Vertex Transitive 5-Connected Graph

Abstract

M.Kriesell conjectured that there existed $b$, $h$ such that every 5-connected graph $G$ with at least $b$ vertices can be contracted to a 5-connected graph $G_0$ such that $0<\left|V\left(G\right)\right|-\left(V\left(G_0\right)\right)<h$. We show that this conjecture holds for vertex transitive 5-connected graphs.

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

All graphs considered here are supposed to be simple, finite, and undirected graphs. For a connected graph $G$, a subset $T\subseteq V\left(G\right)$ is called a smallest separator if $\left|T\right|=\kappa \left(G\right)$ and $G-T$ has at least two components. Let $G$ be a $k$-connected graph, and let $H$ be a subgraph of $G$. Let $G/H$ stand for the graph obtained from $G$ by contracting every component of $H$ to a single vertex and replacing each resulting double edges by a single edge. A subgraph $H$ of $G$ is said to be $k$-contractible if $G/H$ is still $k$-connected. An edge $e$ is a $k$-contractible edge if $G/e$ is $k$-connected; otherwise, we call it a noncontractible edge. Clearly, two end-vertices of a noncontractible edge are contained in some smallest separator. A $k$-connected graph without a $k$-contractible edge is said to be a contraction-critical $k$-connected graph.

Tutte’s [1] wheel theorem showed that every 3-connected graph on more than four vertices contains a 3-contractible edge. For $k\ge 4$, Thomassen and Toft [2] showed that there were infinitely many contraction-critical $k$-regular $k$-connected graphs. On the other hand, one can find that every 4-connected graph can be reduced to a smaller 4-connected graph by contracting at most two edges. Therefore, Kriesell [3] posted the following conjecture.

Conjecture 1.

(see [3]). There exists $b\left(k\right)$, $h\left(k\right)$ such that every $k$-connected graph $G$ with at least $b\left(k\right)$ vertices can be contracted to a k-connected graph $G_0$ such that $0<\left|V\left(G\right)\right|-\left|V\left(G_0\right)\right|<h\left(k\right)$.

Clearly, Conjecture 1 is true for $k\le 4$. By Kriesell’s examples [3], Conjecture 1 fails for $k\ge 6$. Hence, it is still open for $k=5$.

A smallest separator $T$ of a $k$-connected graph is said to be trivial if $G-T$ has exactly two components and one of them has exactly one vertex. A 5-connected graph $G$ is essentially a 6-connected graph if every smallest separator of $G$ is trivial. In ([3]), Kriesell proved the following results.

[figures omitted; refer to PDF]

Theorem 1.

(see [3]). Every essentially 6-connected graph $G$ with at least 13 vertices can be contracted to a 5-connected graph $H$ such that $0<\left|V\left(G\right)\right|-\left|V\left(H\right)\right|<5$.

In this paper, we will show that Conjecture 1 is true for vertex transitive 5-connected graphs. Clearly, Conjecture 1 holds for 5-connected graphs which contain a contractible edge. Hence, in order to show that Conjecture 1 holds for vertex transitive 5-connected graphs, we have to show that all vertex transitive contraction-critical 5-connected graphs have a small contractible subgraph. So, the key point of this paper is to characterize the local structure of a vertex transitive contraction-critical 5-connected graph and, then, to find the contractible subgraph of it. In the following, for convenience, a vertex transitive contraction-critical 5-connected graph will be called a $TCC$-5-connected graph. For a contraction-critical 5-connected graph, there are some results on the local structure of it [4–10].

To state our results, we need to introduce some further definitions. Let $G$ be a 5-connected graph which is 5-regular. For any $x\in V\left(G\right)$, we say that $x$ has one of the following four types according the graph induced by the neighborhood of $x$(see Figures 1(a)–1(d)).

(i)

Type 1: $G\left[N\left(x\right)\right]\cong K_2\cup K_3$

(ii)

Type 2: $G\left[N\left(x\right)\right]\cong C_5$

(iii)

Type 3: $G\left[N\left(x\right)\right]\cong K_2\cup P_2$

(iv)

Type 4: $G\left[N\left(x\right)\right]\cong P_4$

Moreover, for $i\in \left\{\mathrm{1,2,3,4}\right\}$, $G$ has $typei$ if every vertex of $G$ has type $i$.

Furthermore, we need to introduce the graph $G^{\ast }$ (see Figure 1(e)). One can check that $G^{\ast }$ is vertex transitive, and $G^{\ast }$ can be reduced to $K_6$ by contracting $y{x}_1$ and $x{x}_2$.

First, we have the following results on the local structure of $\text{TCC}$-5-connected graphs.

Theorem 2.

Let $G$ be a $\text{TCC}$-5-connected graph. If $\left|V\left(G\right)\right|\le 9$, then either $G\cong K_6$ or $G\cong G^{\ast }$.

Theorem 3.

Let $G$ be a $\text{TCC}$-5-connected graph. If $\left|V\left(G\right)\right|\ge 10$, then $G$ has type 1, type 2, type 3, or type 4.

Theorem 4.

Let $G$ be a $\text{TCC}$-5-connected graph. If $G$ has type 2, then $G$ is isomorphic to icosahedron.

Then, we will prove the following main result of the paper.

Theorem 5.

Let $G$ be a 5-connected vertex transitive graph which is neither $K_6$ nor icosahedron, and then, $G$ can be contracted to a 5-connected $G^{\prime }$ such that $0<\left|V\left(G\right)\right|-\left|V\left(G^{\prime }\right)\right|<3$.

The organization of the paper is as follows. Section 2 contains some preliminary results. In Section 3, we will characterize the local structure of 5-connected $\text{TCC}$-graphs. In Section 4, we will prove Theorem 5.

2. Terminology and Lemma

For terms not defined here, we refer the reader to [11]. Let $G=\left(V\left(G\right),E\left(G\right)\right)$ be a graph, where $V\left(G\right)$ denotes the vertex set of $G$ and $E\left(G\right)$ denotes the edge set of $G$. Let $\text{Aut}\left(G\right)$ denote the automorphism group of $G$, and let $\kappa \left(G\right)$ denote the vertex connectivity of $G$. Let $P_n$ denote a path on $n$ vertices. An edge joining vertices $x$ and $y$ will be written as $xy$. Let $\left[xy\right]$ stand for the new vertex obtained by contracting the edge $xy$. For $x\in V\left(G\right)$, we define $N_G\left(x\right)=\left\{\left.x\right|xy\in E\left(G\right)\right\}$. For $F\subseteq V\left(G\right)$, we define $N_G\left(F\right)={\cup }_{x\in F}{N}_G\left(x\right)-F$. Furthermore, let $G\left[F\right]$ denote the subgraph induced by $F$, and let $G-F$ denote the graph obtained from $G$ by deleting all the vertices of $F$ together with the edges incident with them. Let $\partial \left(F\right)$ stands for the set of edge with one end in $F$ and the other end in $G-F$.

Let $T$ be a smallest separator of a noncomplete connected $G$, and the union of at least one but not of all components of $G-T$ is called a $T$-fragment. A fragment of $G$ is a $T$-fragment for some smallest separator $T$. Let $F$ be a $T$-fragment, and let $\overline{F}=V\left(G\right)-\left(F\cup T\right)$. Clearly, $\overline{F}\ne \varnothing$, and $\overline{F}$ is also a $T$-fragment such that $N_G\left(F\right)=T=N_G\left(\overline{F}\right)$. A fragment with least cardinality is called an atom. For $N_G\left(x\right),d_G\left(x\right)$, and $N_G\left(F\right)$, we often omit the index $G$ if it is clear from the context.

Furthermore, we need some special terminologies for 5-connected graphs. Let $A$ be a fragment of $G$, and let $S=N\left(A\right)$. Let $x\in S$, and $y\in N\left(x\right)\cap A$. A vertex $z$ is said to be an $\text{admissible\hspace{0.17em}vertex}$ of $\left(x,y;A\right)$ if both of the following two conditions hold.$$\begin{array}{c}\text{(1)}& z\in N\left(x\right)\cap N\left(y\right)\cap S\cap V_5\left(G\right),\left|N\left(z\right)\cap A\right|\ge 2.\end{array}$$

A vertex $z$ is said to be an $\text{admissible\hspace{0.17em}vertex}$ of $\left(x;A\right)$, if $z$ is an $\text{admissible\hspace{0.17em}vertex}$ of $\left(x,y;A\right)$ for some $y\in N\left(x\right)\cap A$. Let $\text{Ad}\left(x,y;A\right)$(resp. $\text{Ad}\left(x;A\right)$) stand for the set of admissible vertices of $\left(x,y;A\right)$(resp. $\left(x;A\right)$). Let $e$ be an edge of $G$, and a fragment $A$ is said to be a fragment with respect to $e$ if $V\left(e\right)\subseteq N\left(A\right)$.

The following properties of fragment are well known (for the proof, see [12]), and we will use them without any further reference.

Lemma 1.

(see [12]). Let $F$ and $F^{\prime }$ be two distinct fragments of $G$; $T=N\left(F\right)$, $T^{\prime }=N\left(F^{\prime }\right)$. Then, the following statements hold.

(1)

If $F\cap T^{\prime }\ne \varnothing$, then $\left|F\cap T^{\prime }\right|\ge \left|\overline{F^{\prime }}\cap T\right|,\left|T^{\prime }\cap T\right|\ge \left|\overline{F}\cap T^{\prime }\right|$

(2)

If $F\cap T^{\prime }\ne \varnothing$ and $F\cap T^{\prime }$ is not a fragment of G, then $\overline{F}\cap \overline{F^{\prime }}=\varnothing$ and $\left|F\cap T^{\prime }\right|>\left|\overline{F^{\prime }}\cap T\right|,\left|T^{\prime }\cap T\right|>\left|\overline{F}\cap T^{\prime }\right|$

(3)

If $F\cap T^{\prime }\ne \varnothing \ne \overline{F}\cap \overline{F^{\prime }}$, then both $F\cap T^{\prime }$ and $\overline{F}\cap \overline{F^{\prime }}$ are fragments of G, and $N\left(F\cap T^{\prime }\right)=\left(T^{\prime }\cap T\right)\cup \left(T^{\prime }\cap T\right)\cup \left(F\cap T^{\prime }\right)$

Lemma 2.

(see [4]). Let $G$ be a $k$-connected graph, and $A$ is a fragment of $G$. Let $B\subseteq N\left(A\right)$. If $\left|N\left(B\right)\cap A\right|<\left|B\right|$, then $A=N\left(B\right)\cap A$.

Lemma 3.

(see [5]). Let $G$ be a contraction-critical 5-connected graph, and then, $G$ contains a vertex $x$ such that every edge incident with $x$ is contained in some triangle.

Lemma 4.

(see [6]). Let $G$ be a contraction-critical 5-connected graph. Let $x\in V\left(G\right)$, and $A$ be a fragment such that $x\in N\left(A\right)$, $\left|A\right|\ge 3$, and $\left|\overline{A}\right|\ge 2$. If $\left|N\left(x\right)\cap A\right|=1$, then $\text{Ad}\left(x;A\right)\ne \varnothing$.

Lemma 5.

(see [7]). Let $A$ be a fragment of a contraction-critical 5-connected graph such that $\left|A\right|=2$, and let $t_1,t_2$ be two vertices of $N\left(A\right)$ such that $\left|N\left(t_1\right)\cap A\right|=\left|N\left(t_2\right)\cap A\right|=1$. Then, either $\text{Ad}\left(t_1;A\right)\ne \varnothing$ or $\text{Ad}\left(t_2;A\right)\ne \varnothing$.

Lemma 6.

Let $G$ be a vertex transitive connected graph, and then, for any two vertices $x$ and $y$, $G\left[N\left(x\right)\right]\cong G\left[N\left(y\right)\right]$.

Proof.

Since $G$ is a vertex transitive graph, there exist $g\in \text{Aut}\left(G\right)$ such that $x^g=y$. It follows that ${\left(N\left(x\right)\right)}^g=N\left(y\right)$. Hence, ${\left.g\right|}_{N\left(x\right)}$ is an isomorphic of $G\left[N\left(x\right)\right]$ and $G\left[N\left(y\right)\right]$, where ${\left.g\right|}_{N\left(x\right)}$ is the restriction of $g$ on $N\left(x\right)$.

Lemma 7.

Let $p\ge 2$ be a prime integer, and let $G$ be a vertex transitive graph with $\kappa \left(G\right)=p$; then, $G$ is a $p$-regular graph.

Proof.

To the contrary, we may assume that $\delta \left(G\right)>p$ since $\delta \left(G\right)\ge \kappa \left(G\right)$. It follows that every atom of $G$ has at least two vertices. Since $G$ is a vertex transitive graph, then every vertex of $G$ is contained in some atom.

First, we show that any two atoms of $G$ are disjoint. Otherwise, let $A$ and $B$ be two distinguished atoms of $G$ such that $A\cap B\ne \varnothing$. By the definition of atom, $A\cap B$ is not a fragment. Lemma 1 assures us that $\overline{A}\cap \overline{B}=\varnothing$ and $\left|A\cap N\left(B\right)\right|>\left|\overline{B}\cap N\left(A\right)\right|$. This implies that $\left|A\right|>\left|\overline{B}\right|$, a contradiction. Thus, any two atoms of $G$ are disjoint.

Let $A$ and $C$ be two atoms of $G$ such that $C\cap N\left(A\right)\ne \varnothing$. It follows that $A\cap C=\varnothing$. We show that $C\subseteq N\left(A\right)$. Otherwise, suppose $C\cap \overline{A}\ne \varnothing$. If $C\cap \overline{A}$ is a fragment of $G$, then we see that $\left|C\cap \overline{A}\right|<\left|C\right|$, since $C\cap N\left(A\right)\ne \varnothing$. This contradicts the definition of atom. So, $C\cap \overline{A}$ is not a fragment of $G$. Lemma 1 assures us that $A\cap \overline{C}=\varnothing$ and $\left|C\cap N\left(A\right)\right|>\left|A\cap N\left(C\right)\right|=\left|A\right|$. It follows that $\left|C\right|>\left|A\right|$, a contradiction. Hence, $C\subseteq N\left(A\right)$. Therefore, $N\left(A\right)$ is the disjoint union of some atom, since any two atoms of $G$ are disjoint and every vertex of $G$ is contained in some atom. This means that $\left|A\right|$ is a subdivision of $\left|N\left(A\right)\right|$, and hence, $\left|A\right|=p$. It follows that $N\left|A\right|=C$. By symmetry, we see that $N\left(C\right)=A$, which implies that $\overline{A}=\varnothing$, a contradiction.

Lemma 8.

Let $G$ be a $\text{TCC}$-5-connected graph. If $G$ does not contain $K_4$ as subgraph, then for any $x\in V\left(G\right)$, $\mathrm{\Delta }\left(G\left[N\left(x\right)\right]\right)\le 2$.

Proof.

Clearly, Lemma 7 assures us that $G$ is 5-regular, which implies that $G$ has an even order. Suppose that $x\in V\left(G\right)$ with $N\left(x\right)=\left\{x_1,\dots ,x_5\right\}$ such that $x_1$ adjacent to at least three vertices of $N\left(x\right)$. Let $A=\left\{x\right\}$, and it follows $N\left(A\right)=N\left(x\right)$. If $G-A-N\left(A\right)=\varnothing$, then $G$ has six vertices. It follows that $G\cong K_6$, which implies $G$ contains $K_4$, a contradiction. Hence, we may assume that $G-A-N\left(A\right)\ne \varnothing$. It follows that $A$ is a fragment of $G$. By symmetry, we assume that $\left\{x_2,x_3,x_4\right\}\subseteq N\left(x_1\right)$. Now, we observe that $N\left(x_1\right)\cap N\left(A\right)=\left\{x_2,x_3,x_4\right\}$ and $\left|N\left(x_1\right)\cap \overline{A}\right|=1$. Let $N\left(x_1\right)\cap \overline{A}=\left\{t_1\right\}$. Let $B=\left\{x,x_1\right\}$, and then $N\left(B\right)=\left\{x_2,\dots ,x_5,t_1\right\}$. Now, the fact that $\left|V\left(G\right)\right|$ is even assures us that $G-B-N\left(B\right)\ne \varnothing$. It follows that $B$ is a fragment of $G$. Furthermore, we see that $N\left(t_1\right)\cap B=\left\{x_1\right\}$ and $N\left(x_5\right)\cap B=\left\{x\right\}$.Now, Lemma 5 assures us that either $\text{Ad}\left(t_1;B\right)\ne \varnothing$ or $\text{Ad}\left(x_5;B\right)\ne \varnothing$. If $\text{Ad}\left(x_5;B\right)\ne \varnothing$, then without loss of generality, assume $x_2\in \text{Ad}\left(x_5;B\right)$. Therefore, $G\left[N\left(x\right)\right]$ is a connected graph. If $\text{Ad}\left(t_1;B\right)\ne \varnothing$, then, similarly, we have that $G\left[N\left(x\right)\right]$ is a connected graph. Now, since $G$ is vertex transitive, the following claims hold.

Claim 1.

For any $t\in V\left(G\right)$, $G\left[N\left(t\right)\right]$ is a connected graph.

Claim 2.

For any $t\in V\left(G\right)$, $G\left[N\left(t\right)\right]$ contains a cycle of length 4.

Proof.

Since $G$ is a vertex transitive graph, we only show that $N\left(x_1\right)$ has a cycle of length 4. By Claim 1, we see that for $y\in N\left(B\right),N\left(y\right)\cap N\left(B\right)\ne \varnothing$. On the other hand, we observe that $G\left[\left\{x_2,x_3,x_4\right\}\right]\cong {\overline{K}}_3$, since $G$ does not contain $K_4$. This implies that every member of $\left\{x_2,x_3,x_4\right\}$ is either adjacent to $t_1$ or $x_5$. It follows that $\left|N\left(t_1\right)\cap \left\{x_2,x_3,x_4\right\}\right|\ge 2$ or $\left|N\left(x_5\right)\cap \left\{x_2,x_3,x_4\right\}\right|\ge 2$. By symmetry, we may assume that $\left|N\left(t_1\right)\cap \left\{x_2,x_3,x_4\right\}\right|\ge 2$. It follows that $G\left[N\left(x_1\right)\right]$ contains a cycle of length 4. Hence, for any $t\in V\left(G\right)$, $G\left[N\left(t\right)\right]$ has a cycle of length 4.

Now, we are ready to complete the proof of Lemma 8. By Claim 2, we see that $\left|N\left(x_i\right)\cap N\left(B\right)\right|\ge 2$ for $i\in \left\{\mathrm{2,3,4}\right\}$. This implies that $\left\{t_1,x_5\right\}\subseteq N\left(x_2\right)\cap N\left(x_3\right)\cap N\left(x_4\right)$. Now, we see that every vertex of $N\left(B\right)$ is adjacent to exactly one vertex of $\overline{A}$. If $\left|\overline{B}\right|=1$, say $\overline{B}=\left\{t\right\}$, then $G\left[N\left(t\right)\right]\cong K_{\mathrm{2,3}}$ and $G\left[N\left(x_2\right)\right]\cong C_5$, a contradiction. If $\left|\overline{B}\right|=2$, we can observe that $\overline{B}$ has a vertex with a degree of at most 4, a contradiction. Hence, we may assume that $\left|\overline{B}\right|=3$. Now, Lemma 4 shows that $\text{Ad}\left(x_2;\overline{B}\right)\ne \varnothing$, which implies $\left|N\left(z\right)\cap \overline{A}\right|\ge 2$ for some $z\in N\left(B\right)$, a contradiction.

Lemma 9.

Let $G$ be a $\text{TCC}$-5-connected graph. If $G$ has type 4, then $G$ is essentially 6-connected.

Proof.

Since $G$ has type 4, we see that for any $x\in V\left(G\right)$, $\mathrm{\Delta }\left(G\left[N\left(x\right)\right]\right)\le 2$.

Claim 3.

If $A$ is a fragment of $G$, then $\left|A\right|\ne 2$.

Proof.

Suppose $A=\left\{x,y\right\}$. If $xy\in E\left(G\right)$, then $x$ has three neighbors in $G\left[N\left(y\right)\right]$, a contradiction. So, we may assume $xy\notin E\left(G\right)$. It follows that $G\left[N\left(A\right)\right]\cong P_5$. Let $x_1{x}_2{x}_3{x}_4{x}_5$ be the path of $G\left[N\left(A\right)\right]$. It follows that $\left|N\left(x_2\right)\cap \overline{A}\right|=\left|N\left(x_3\right)\cap \overline{A}\right|=\left|N\left(x_4\right)\cap \overline{A}\right|=1$. If $\left|\overline{A}\right|\ge 3$, then Lemma 4 implies that $\text{Ad}\left(x_3,\overline{A}\right)\ne \varnothing$. Hence, either $x_2\in \text{Ad}\left(x_3,\overline{A}\right)$ or $x_4\in \text{Ad}\left(x_3,\overline{A}\right)$. This is a contradiction, since $\left|N\left(x_2\right)\cap \overline{A}\right|=\left|N\left(x_4\right)\cap \overline{A}\right|=1$. Hence, we may assume that $\left|\overline{A}\right|\le 2$. If $\left|\overline{A}\right|=1$, then we see that $d\left(x_1\right)<5$, a contradiction. So, we may assume $\left|\overline{A}\right|=2$. It follows that $\left|V\left(G\right)\right|=9$, which contradicts the fact that $G$ has an even order. Hence, Claim 3 holds.

Claim 4.

If $A$ is a fragment of $G$, then $\left|\overline{A}\right|\ne 3$.

Proof.

We first show that $G\left[A\right]$ is a connected graph. Otherwise, let $A_1$ be a component of $G\left[A\right]$ such that $A_1$ has exactly one vertex. It follows that $A_2=A-A_1$ is a fragment of cardinality 2, a contradiction. Next, we show that $G\left[A\right]$ is a path. Suppose $G\left[A\right]$ is a cycle, then a simple calculation shows that $\left|\partial \left(A\right)\right|=9$. This implies that one vertex of $N\left(A\right)$, say $w$, has exactly one neighbor in $A$. Now, we find that $A-N\left(w\right)$ is a fragment of cardinality 2, a contradiction.

Let $xyz$ be the path of $G\left[A\right]$, and let $N\left(A\right)=\left\{x_1,\dots ,x_5\right\}$. Without the loss of generality, let $N\left(y\right)=\left\{x,x_1,x_2,x_3,z\right\}$.

 

Subclaim 1. $\left|N\left(x\right)\cap \left\{x_1,x_2,x_3\right\}\right|=2$ and $\left|N\left(z\right)\cap \left\{x_1,x_2,x_3\right\}\right|=2$.

 

Proof. Notice that $G$ has type 4; we find that $\left|N\left(x\right)\cap \left\{x_1,x_2,x_3\right\}\right|\le 2$. If $\left|N\left(x\right)\cap \left\{x_1,x_2,x_3\right\}\right|\le 1$, then we find that $d\left(x\right)\le 4$, a contradiction. Hence, $\left|N\left(x\right)\cap \left\{x_1,x_2,x_3\right\}\right|=2$. By symmetry, $\left|N\left(z\right)\cap \left\{x_1,x_2,x_3\right\}\right|=2$.

 

Without the loss of generality, we may assume that $\left\{x_1,x_2\right\}\subseteq N\left(x\right)$. Now, if $\left\{x_1,x_2\right\}\subseteq N\left(z\right)$, then $x{x}_{1}z{x}_{2}x$ is a cycle of $G\left[N\left(y\right)\right]$, a contradiction. Therefore, $\left\{x_2,x_3\right\}\subseteq N\left(z\right)$, which implies that $\left\{x_4,x_5\right\}\subseteq N\left(x\right)\cap N\left(z\right)$.

 

Subclaim 2. $G\left[\left\{x_1,x_2,x_3\right\}\right]\cong \overline{K_3}$.

 

Proof. If $x_1{x}_2\in E\left(G\right)$, then $N\left(y\right)$ has a triangle, a contradiction. It follows that $x_1{x}_2\notin E\left(G\right)$. Similarly, we have $x_2{x}_3\notin E\left(G\right)$. Furthermore, if $x_1{x}_3\notin E\left(G\right)$, then we find that there is a cycle of length four in $N\left(y\right)$, a contradiction. Thus, $x_1{x}_3\notin E\left(G\right)$. It follows that $G\left[\left\{x_1,x_2,x_3\right\}\right]\cong \overline{K_3}$.

Now, we are ready to complete the proof of Claim 4. Focusing on $x_2$, we find that $N\left(x_2\right)\cap N\left(A\right)\ne \varnothing$ since $G\left[N\left(x_2\right)\right]$ is connected. By Subclaim 2, we may assume that $x_4\in N\left(x_2\right)$. Now, we find that there is a cycle of length four in $N\left(x_2\right)$, a contradiction.

Claim 5.

For every smallest separator $T$, $G-T$ has exactly two components.

Proof.

Otherwise, assume that $G-T$ has at least three components. Let $A_1$, $A_2$, and $A_3$ be three connected components of $G-T$.

 

Subclaim 3. For any $y\in T$, $\left|N\left(y\right)\cap T\right|=2$, and $\left|N\left(y\right)\cap A_i\right|=1,i\in \left\{\mathrm{1,2,3}\right\}$.

 

Proof. Let $y\in T$, let $N\left(y\right)=\left\{y_1,\dots ,y_5\right\}$. Without the loss of generality, we may assume that $y_i\in A_i,i\in \left\{\mathrm{1,2,3}\right\}$. Now, we find that $N\left(y\right)\cap T\ne \varnothing$, since $G$ has type 4. Suppose $y_4\in N\left(y\right)\cap T$. If $N\left(y\right)\cap T=\left\{y_4\right\}$, then the fact that $G\left[N\left(y\right)\right]$ is connected shows that $y_4$ has three neighbors in $G\left[N\left(y\right)\right]$, which contradicts the fact that $G$ has type 4. So, we have $N\left(y\right)\cap T=\left\{y_4,y_5\right\}$. It follows that $\left|N\left(y\right)\cap A_i\right|=1,i\in \left\{\mathrm{1,2,3}\right\}$ and $\left|N\left(y\right)\cap T\right|=2$.

By Subclaim 3, $\delta \left(G\left[T\right]\right)=2$, which implies that $G\left[T\right]$ is a cycle of length 5. Hence, we see that $\left|A_i\right|\ne 1,i\in \left\{\mathrm{1,2,3}\right\}$. Furthermore, by Subclaims 3 and 4, $\left|A_i\right|\ne 3$ for each $i=\mathrm{1,2,3}$. Focusing on $A_1$, we find that ${\overline{A}}_1=A_2\cup A_3$, which implies that $\left|{\overline{A}}_1\right|\ge 6$. Recall that $\left|N\left(x\right)\cap A_1\right|=1$, and Lemma 4 shows that $\text{Ad}\left(x;A_1\right)\ne \varnothing$. Without the loss of generality, assume that $y\in \text{Ad}\left(x;A_1\right)$. This implies that $\left|N\left(y\right)\cap A_1\right|\ge 2$, which contradicts Subclaim 3. Hence, Claim 5 holds.

Next, we assume that $G$ is not essentially 6-connected. It follows that there is a fragment $B$ such that $\left|B\right|\ge 2$ and $\left|\overline{B}\right|\ge 2$. Let $\mathrm{ℬ}=\left\{\left.B\right|B\right.$ is a fragment such that $\left|B\right|\ge 2$ and $\left.\left|\overline{B}\right|\ge 2\right\}$, and let $t=\min \left\{\left|\left.B\right|\right|B\in \mathrm{ℬ}\right\}$. By Claims 3 and 4, we see that $t\ge 4$. Let ${\mathrm{ℬ}}_1=\left\{\left.B\right|B\in \mathrm{ℬ}\right.$ and $\left.\left|B\right|=t\right\}$. Let $A\in {\mathrm{ℬ}}_1$, and let $y\in N\left(A\right)$. Now, since $G$ is vertex transitive, every vertex of $G$ is contained in some member of ${\mathrm{ℬ}}_1$. Therefore, there exist $B\in {\mathrm{ℬ}}_1$ such that $y\in B$. Next, we will analyse the local structure of $A$ and $B$.

Claim 6.

If $A\cap B\ne \varnothing$, then $\overline{A}\cap \overline{B}\ne \varnothing$.

Proof.

Suppose $A\cap B\ne \varnothing$ and $\overline{A}\cap \overline{B}=\varnothing$. Now, Lemma 1 assures us that $\left|A\cap N\left(B\right)\right|\ge \left|\overline{B}\cap N\left(A\right)\right|$. It follows that$$\begin{array}{c}\text{(2)}& \left|A\right|=\left|A\cap B\right|+\left|A\cap N\left(B\right)\right|+\left|A\cap \overline{B}\right|\ge \left|A\cap B\right|+\left|\overline{B}\cap N\left(A\right)\right|+\left|A\cap \overline{B}\right|\\ >\left|\overline{B}\cap N\left(A\right)\right|+\left|A\cap \overline{B}\right|=\left|\overline{B}\right|.\end{array}$$

This contradicts the choice of $A$.

Claim 7.

$A\cap \overline{B}\ne \varnothing$ if and only if $\overline{A}\cap B\ne \varnothing$.

Proof.

Suppose $A\cap \overline{B}\ne \varnothing$. Now, Lemma 1 assures us that $\left|A\cap N\left(B\right)\right|\ge \left|B\cap N\left(A\right)\right|$. If $\overline{A}\cap B=\varnothing$, then we see that$$\begin{array}{c}\text{(3)}& \left|A\right|=\left|A\cap B\right|+\left|A\cap N\left(B\right)\right|+\left|A\cap \overline{B}\right|\ge \left|A\cap B\right|+\left|B\cap N\left(A\right)\right|+\left|A\cap \overline{B}\right|\\ >\left|A\cap B\right|+\left|B\cap N\left(A\right)\right|=\left|B\right|.\end{array}$$

This contradicts the choice of $A$. Hence, we see that $\overline{A}\cap B\ne \varnothing$. By symmetry, we see that $\overline{A}\cap B\ne \varnothing$ implies $A\cap \overline{B}\ne \varnothing$.

Claim 8.

$A\cap B=\varnothing$.

Proof.

Suppose $A\cap B\ne \varnothing$. By Claim 6, we know that $\overline{A}\cap \overline{B}\ne \varnothing$. Hence, $A\cap B$ is a fragment of $G$. By the choice of $A$, we know that $\left|A\cap B\right|=1$. Furthermore, since $\overline{A}\cap \overline{B}\ne \varnothing$, Lemma 1 assures us that $\left|\overline{B}\cap N\left(A\right)\right|\ge \left|A\cap N\left(B\right)\right|$.

If $A\cap \overline{B}=\varnothing$, then Claim 7 assures us that $\overline{A}\cap B=\varnothing$. Furthermore, $\left|A\right|=\left|B\right|\ge 4$ implies that $\left|A\cap N\left(B\right)\right|=\left|B\cap N\left(A\right)\right|\ge 3$. Hence, we find that $\left|N\left(A\right)\right|\ge \left|B\cap N\left(A\right)\right|+\left|\overline{B}\cap N\left(A\right)\right|\ge \left|B\cap N\left(A\right)\right|+\left|A\cap N\left(B\right)\right|\ge 6$, a contradiction.

So, we may assume $A\cap \overline{B}\ne \varnothing$. Then, Claim 7 assures us that $\overline{A}\cap B\ne \varnothing$. Hence, both $A\cap \overline{B}$ and $B\cap \overline{A}$ are fragments of $G$. By the choice of $A$ and $B$, we know that $\left|A\cap \overline{B}\right|=\left|B\cap \overline{A}\right|=1$. It follows that $\left|A\cap N\left(B\right)\right|=\left|B\cap N\left(A\right)\right|$.

Since $\overline{A}\cap \overline{B}\ne \varnothing$, Lemma 1 assure us that $\left|\overline{B}\cap N\left(A\right)\right|\ge \left|A\cap N\left(B\right)\right|$. If $\left|A\cap N\left(B\right)\right|\ge 3$, then $\left|N\left(A\right)\right|\ge \left|B\cap N\left(A\right)\right|+\left|\overline{B}\cap N\left(A\right)\right|\ge 6$, a contradiction.

Therefore, let $\left|A\cap N\left(B\right)\right|=2$. It follows that $\left|A\cap N\left(B\right)\right|=\left|B\cap N\left(A\right)\right|=2$. Since $\overline{A}\cap \overline{B}\ne \varnothing$ and $A\cap B\ne \varnothing$, Lemma 1 assures us that $\left|\overline{A}\cap N\left(B\right)\right|=\left|\overline{B}\cap N\left(A\right)\right|=2$. This implies that $\left|N\left(B\right)\cap N\left(A\right)\right|=1$. Let $N\left(B\right)\cap N\left(A\right)=\left\{t\right\}$. Now, $N\left(t\right)\cap A\cap B\ne \varnothing$, since $A\cap B$ is a fragment. Similarly, we find that $N\left(t\right)\cap A\cap \overline{B}\ne \varnothing$, $N\left(t\right)\cap \overline{A}\cap \overline{B}\ne \varnothing$, and $N\left(t\right)\cap \overline{A}\cap B\ne \varnothing$. Now, we find that $G\left[N\left(t\right)\right]$ has at least two components, a contradiction.

Claim 9.

$A\cap \overline{B}=\varnothing$ and $B\cap \overline{A}=\varnothing$.

Proof.

Suppose $A\cap \overline{B}\ne \varnothing$. By Claim 7, we see that $\overline{A}\cap B\ne \varnothing$. Hence, both $A\cap \overline{B}$ and $\overline{A}\cap B$ are fragments of $G$. By the choice of $A$, we see that $\left|A\cap \overline{B}\right|=\left|\overline{A}\cap B\right|=1$. It follows that $\left|A\cap N\left(B\right)\right|=\left|B\cap N\left(A\right)\right|\ge 3$.

If $\overline{A}\cap \overline{B}\ne \varnothing$, then $\left|\overline{B}\cap N\left(A\right)\right|\ge \left|A\cap N\left(B\right)\right|$. Hence, we see that $\left|N\left(A\right)\right|\ge \left|B\cap N\left(A\right)\right|+\left|\overline{B}\cap N\left(A\right)\right|\ge 6$, a contradiction.

Hence, we may assume that $\overline{A}\cap \overline{B}=\varnothing$. Then, by the choice of $B$, we know that $\left|\overline{B}\right|\ge \left|B\right|$. It follows that $\left|\overline{B}\cap N\left(A\right)\right|\ge 3$. Hence, we find that $\left|N\left(A\right)\right|\ge \left|B\cap N\left(A\right)\right|+\left|\overline{B}\cap N\left(A\right)\right|\ge 6$, a contradiction.

Now, we are ready to complete the proof of the Lemma. By Claims 8 and 9, we find that $A=A\cap N\left(B\right)$ and $B=B\cap N\left(A\right)$. Now, we find that $\left|\overline{B}\cap N\left(A\right)\right|\le \left|N\left(A\right)\right|-\left|B\cap N\left(A\right)\right|\le 1$, since $\left|B\cap N\left(A\right)\right|=\left|B\right|\ge 4$. It follows that $\left|\overline{B}\cap N\left(A\right)\right|<\left|A\cap N\left(B\right)\right|$. Now, Lemma 1 implies that $\overline{A}\cap \overline{B}=\varnothing$. It follows that $\left|\overline{B}\right|=\left|\overline{B}\cap N\left(A\right)\right|\le 1$, a contradiction.

3. The Local Structure of TCC-5-Connected Graphs

In this section, since Lemma 7 holds, all TCC-5-connected graphs were supposed to be 5-regular and have an even order.

Theorem 6.

Let $G$ be a TCC-5-connected $\text{graph}$. If $\left|V\left(G\right)\right|\le 9$, then either $G\cong K_6$ or $G\cong G^{\ast }$.

Proof.

Recall that $G$ has an even order. It follows that either $\left|V\left(G\right)\right|=6$ or $\left|V\left(G\right)\right|=8$. If $\left|V\left(G\right)\right|=6$, then $G\cong K_6$. So, we may assume $\left|V\left(G\right)\right|=8$. It follows that $G$ has a fragment of cardinality 2. Let $A=\left\{x,y\right\}$ be a fragment of $G$. Let $N\left(A\right)=\left\{x_1,x_2,x_3,x_4,x_5\right\}$, and let $\overline{A}=\left\{z\right\}$.

Claim 10.

$xy\in E\left(G\right)$.

Proof.

Otherwise, we find that $G\left[N\left(A\right)\right]\cong C_5$. It follows that $G\left[N\left(x\right)\right]\cong C_5$. On the other hand, $G\left[N\left(x_1\right)\right]\cong \overline{K_3}\times \overline{K_2}$. It follows that $G\left[N\left(x\right)\right]\cancel{\cong }G\left[N\left(x_1\right)\right]$, a contradiction.

Let $N\left(x\right)=\left\{x_1,x_2,x_3,x_4,y\right\}$. By symmetry, we may assume that $N\left(y\right)=\left\{x_1,x_2,x_3,x_5,x\right\}$. We find that $y$ has at least three neighbors in $G\left[N\left(x\right)\right]$. Hence, Lemma 8 implies that $G$ contains $K_4$. It follows that $G\left[N\left(x\right)\right]$ contains a triangle.

Claim 11.

$x_4{x}_5\in E\left(G\right)$.

Proof.

Suppose $x_4{x}_5\notin E\left(G\right)$. Notice that for $i\in \left\{\mathrm{4,5}\right\}$, $\left|N\left(x_i\right)\cap \left(A\cup \overline{A}\right)\right|=2$, we see that $\left\{x_4,x_5\right\}\subseteq N\left(x_1\right)\cap N\left(x_2\right)\cap N\left(x_3\right)$. Therefore, $G\left[\left\{x_1,x_2,x_3\right\}\right]\cong \overline{K_3}$, which implies that $G\left[N\left(x\right)\right]$ does not contain a triangle, a contradiction.

Now, we observe that $G\left[N\left(A\right)\right]-x_4{x}_5$ is 2-regular. Hence, $G\left[N\left(A\right)\right]-x_4{x}_5$ is a cycle of length 5. Now, by symmetry, we may assume that $\left\{x_2,x_3\right\}\subseteq N\left(x_4\right)$ and $\left\{x_1,x_2\right\}\subseteq N\left(x_5\right)$. It follows that $x_1{x}_3\in E\left(G\right)$ since $G\left[N\left(A\right)\right]-x_4{x}_5$ is a cycle of length 5. Therefore, we have $G\cong G^{\ast }$.

Lemma 10.

Let $G$ be a $\text{TCC}$-5-connected $graph$ with $\left|V\left(G\right)\right|\ge 10$. If $G$ contains $K_4$ as a subgraph, then $G$ has type 1.

Proof.

Since $G$ is a vertex transitive graph, we know that every vertex of $G$ is contained in a $K_4$. Let $x$ be a vertex of $G$, and let $N\left(x\right)=\left\{x_1,\dots ,x_5\right\}$. Without the loss of generality, let $G\left[\left\{x,x_1,x_2,x_3\right\}\right]\cong K_4$.

Claim 12.

$\left|N\left(x_i\right)\cap \left\{x_1,x_2,x_3\right\}\right|\le 1,i\in \left\{\mathrm{4,5}\right\}$.

Proof.

We only show that $\left|N\left(x_4\right)\cap \left\{x_1,x_2,x_3\right\}\right|\le 1$, and the other one can be handled similarly. Otherwise, by symmetry, we may assume $\left\{x_1,x_2\right\}\subseteq N\left(x_4\right)$. Let $N\left(x_1\right)=\left\{x,x_2,x_3,x_4,x_1\right\}$. Let $A=\left\{x,x_1\right\}$, and it follows that $N\left(A\right)=\left\{x_2,x_3,x_4,x_5,t_1\right\}$. Furthermore, recall that $\left|V\left(G\right)\right|\ge 10$, $G-A-N\left(A\right)\ne \varnothing$. If $t_1=x_5$, then $N\left(A\right)$ is a separator of order 4, a contradiction. Thus, $t_1\ne x_5$. Therefore, $A$ is a fragment of $G$. Furthermore, since $\left|V\left(G\right)\right|\ge 10$, we see that $\left|\overline{A}\right|\ge 3$. Let $B=\left\{x,x_2\right\}$, and let $N\left(x_2\right)=\left\{x,x_2,x_3,x_4,t_2\right\}$, where $t_2\in N\left(x_2\right)\cap \overline{A}$. Similarly, $B$ is a fragment of $G$ such that $N\left(B\right)=\left\{x_1,x_3,x_4,x_5,t_2\right\}$. Furthermore, we have $\left|\overline{A}\right|=\left|\overline{B}\right|$.

Notice that $t_2\in \overline{A}$ and $t_1\in N\left(A\right)$, we see that $t_1\ne t_2$. Now, we see that $A\cap B=\left\{x\right\}$, $A\cap N\left(B\right)=\left\{x_1\right\}$, $B\cap N\left(A\right)=\left\{x_2\right\}$, $N\left(A\right)\cap N\left(B\right)=\left\{x_3,x_4,x_5\right\}$, $\overline{A}\cap N\left(B\right)=\left\{t_2\right\}$, and $\overline{B}\cap N\left(A\right)=\left\{t_1\right\}$.

Now, since $\left|\overline{A}\right|=\left|\overline{B}\right|\ge 3$, we find that $\left|\overline{A}\cap \overline{B}\right|\ge 2$. Let $C=A\cup B$. Clearly, $C$ is a fragment with $\overline{C}=\overline{A}\cap \overline{B}$. Notice that $N\left(t_1\right)\cap C=\left\{x_1\right\}$, $N\left(t_2\right)\cap C=\left\{x_2\right\}$, and $N\left(x_5\right)\cap C=\left\{x\right\}$. Now, Lemma 4 implies that $\text{Ad}\left(t_1;C\right)\cup \text{Ad}\left(t_2;C\right)\cup \text{Ad}\left(x_5;C\right)\subseteq \left\{x_3,x_4\right\}$. It follows that either $x_3$ or $x_4$ has two neighbors in $N\left(C\right)$. By symmetry, let $x_3$ have two neighbors in $N\left(C\right)$. It follows that $d\left(x_3\right)\ge 6$, a contradiction. Hence, Claim 12 holds.

Claim 13.

$N\left(x_i\right)\cap \left\{x_1,x_2,x_3\right\}=\varnothing ,i\in \left\{\mathrm{4,5}\right\}$.

Proof.

We only show that $N\left(x_4\right)\cap \left\{x_1,x_2,x_3\right\}=\varnothing$, and the other one can be handled similarly. Otherwise, by symmetry, we may assume that $x_4{x}_1\in E\left(G\right)$. Now, by Claim 12, $N\left(x_4\right)\cap \left\{x_2,x_3\right\}=\varnothing$. Let $A=\left\{x,x_1\right\}$ and $N\left(x_1\right)=\left\{x,x_2,x_3,x_4,t_1\right\}$. Clearly, $N\left(A\right)=\left\{x_2,x_3,x_4,x_5,t_1\right\}$ and $G-A-N\left(A\right)\ne \varnothing$. Now, since $G$ is 5-connected, we observe that $t_1\ne x_5$. Therefore, $A$ is a fragment of $G$.

 

Subclaim 4. $N\left(x_5\right)\cap \left\{x_2,x_3\right\}=\varnothing$.

 

Proof. Suppose $x_2{x}_5\in E\left(G\right)$, and then, $\left\{x,x_2\right\}$ is fragments of $G$. Furthermore, we see that $G\left[N\left(x\right)\right]$ is a connected graph, and this implies that for any $t\in V\left(G\right)$, $G\left[N\left(t\right)\right]$ is a connected graph. Let $B=\left\{x,x_2\right\}$, and it follows $N\left(B\right)=\left\{x_1,x_3,x_4,x_5,t_2\right\}$, where $t_2\in N\left(x_2\right)-\left\{x,x_1,x_3,x_5\right\}$. Now, since $G$ is 5-connected, we see that $t_2\ne x_4$. We observe that $A\cap B=\left\{x\right\}$, $A\cap N\left(B\right)=\left\{x_1\right\}$, $B\cap N\left(A\right)=\left\{x_2\right\}$, $N\left(A\right)\cap N\left(B\right)=\left\{x_3,x_4,x_5\right\}$, $\overline{A}\cap N\left(B\right)=\left\{t_2\right\}$, and $\overline{B}\cap N\left(A\right)=\left\{t_1\right\}$. Furthermore, we see that $A\cap \overline{B}=\varnothing$ and $B\cap \overline{A}=\varnothing$. Notice that $G\left[N\left(x\right)\right]$ is connected, and we see that for every vertex $t$ of $G$, $G\left[N\left(t\right)\right]$ is connected.

Now, since $A\cap \overline{B}=\varnothing$ and $\overline{B}\cap N\left(A\right)=\left\{t_1\right\}$, the fact $\left|\overline{A}\right|=\left|\overline{B}\right|\ge 3$ shows that $\left|\overline{A}\cap \overline{B}\right|\ge 2$. Furthermore, $\overline{A}\cap \overline{B}$ is a fragment.

If $\left|N\left(x_3\right)\cap \overline{A}\cap \overline{B}\right|\ge 2$, then $G\left[N\left(x_3\right)\right]$ has at least two components, a contradiction. Therefore, $\left|N\left(x_3\right)\cap \left(\overline{A}\cap \overline{B}\right)\right|=1$ and $N\left(x_3\right)\cap N\left(\overline{A}\cap \overline{B}\right)\ne \varnothing$.

On the other hand, by Claim 12, $N\left(x_4\right)\cap \left\{x_1,x_2,x_3\right\}=\left\{x_1\right\}$, and $N\left(x_5\right)\cap \left\{x_1,x_2,x_3\right\}=\left\{x_2\right\}$. This fact implies that either $x_3{t}_1\in E\left(G\right)$ or $x_3{t}_2\in E\left(G\right)$.

By symmetry, we may assume $x_3{t}_1\in E\left(G\right)$. Now, since $N\left(x_3\right)\cap \overline{A}\cap \overline{B}\ne \varnothing$, we see that $G\left[N\left(x_3\right)\right]$ has only one vertex of degree 3. On the other hand, we find that $G\left[N\left(x\right)\right]$ has two vertex of degree 3, and this implies that $G\left[N\left(x_3\right)\right]\cancel{\cong }G\left[N\left(x\right)\right]$, a contradiction. This contradiction shows that $x_2{x}_5\notin E\left(G\right)$. By symmetry, $x_3{x}_5\notin E\left(G\right)$. Hence, Subclaim 4 holds.

 

Subclaim 5. $x_4{x}_5\notin E\left(G\right)$.

 

Proof. Suppose $x_4{x}_5\notin E\left(G\right)$. Let $P\prime$ be a graph which is got from the path $x_3{x}_2{x}_1{x}_4{x}_5$ by adding the edge $x_1{x}_3$. Clearly, $G\left[N\left(x\right)\right]\cong P\prime$. Now, since $G\left[N\left(x\right)\right]\cong G\left[N\left(x_1\right)\right]$, we find that $x_4{t}_1\in E\left(G\right)$. This implies that $\left|N\left(x_4\right)\cap \overline{A}\right|=1$. Let $N\left(x_4\right)\cap \overline{A}=\left\{t_4\right\}$. Furthermore, $G\left[N\left(x_4\right)\right]$ has a triangle, since $G\left[N\left(x\right)\right]$ has a triangle. Therefore, $G\left[\left\{t_1,t_4,x_5\right\}\right]$ is a triangle. It follows that $G\left[N\left(x_4\right)\right]$ has a Hamilton cycle. This implies that $G\left[N\left(x\right)\right]\cancel{\cong }G\left[N\left(x_4\right)\right]$, a contradiction. Thus, Subclaim 5 holds.

By Subclaims 4 and 5, $G\left[N\left(x\right)\right]$ has two components, and one of them has exactly one vertex. If $\left|N\left(x_4\right)\cap \overline{A}\right|=3$, then $G\left[N\left(x\right)\right]\cancel{\cong }G\left[N\left(x_4\right)\right]$, a contradiction. So, assume that $\left|N\left(x_4\right)\cap \overline{A}\right|\le 2$, which implies that $N\left(x_4\right)\cap N\left(A\right)\ne \varnothing$. By Claim 12 and Subclaim 5, $N\left(x_4\right)\cap N\left(A\right)=\left\{t_1\right\}$. Now, we see that $K_4$ which contains $x_4$ is contained in $N\left(A\right)\cup \overline{A}$. Hence, $G\left[N\left(x_4\right)\right]$ is a connected graph, a contradiction. Thus, Claim 13 holds.

By Claim 13 and Lemma 3, $x_4{x}_5\in E\left(G\right)$, and hence, $x$ has type 1. Therefore, $G$ has type 1.

Theorem 7.

Let $G$ be a TCC-5-connected $\text{graph}$. If $\left|V\left(G\right)\right|\ge 10$, then $G$ has type 1, type 2, type 3, or type 4.

Proof.

If $G$ contains $K_4$, then Lemma 10 assures us that $G$ has type 1. So, we may assume that $G$ does not contain $K_4$. Hence, Lemma 8 assures us that for any $x\in V\left(G\right)$, $\mathrm{\Delta }\left(G\left[N\left(x\right)\right]\right)\le 2$. Now, Lemma 3 assures us that $G$ has either type 2 or type 3 or type 4.

Theorem 8.

Let $G$ be a TCC-5-connected $\text{graph}$. If $G$ has type 2, then $G$ is isomorphic to icosahedron.

Proof.

Let $N\left(x\right)=\left\{x_1,\dots ,x_5\right\}$, and let $x_1{x}_2\cdots x_5{x}_1$ be the cycle of $G\left[N\left(x\right)\right]$. Furthermore, let $N\left(x_3\right)=\left\{x_2,x,x_4,y_1,y_2\right\}$. Since $G$ has type 2, we may assume that $x_{2}x{x}_4{y}_2{y}_1{x}_2$ is a cycle of $G\left[N\left(x_3\right)\right]$. Let $N\left(x_2\right)=\left\{x_1,x,x_3,y_1,y_3\right\}$, and then $y_3\ne y_2$ and $y_3\notin \left\{x_1,\dots ,x_5\right\}$. Now, $x_{1}x{x}_3{y}_1{y}_3{x}_1$ is a cycle of $G\left[N\left(x_2\right)\right]$. Let $N\left(x_4\right)=\left\{x_3,x,x_5,y_4,y_2\right\}$. If $y_4=y_3$, then, since $G$ has type 2, $\left\{x_1,x_2,x_4,x_5,y_1,y_2\right\}\subseteq N\left(y_3\right)$. This implies that $d\left(y_3\right)\ge 6$, a contradiction. Hence, we have $y_4\ne y_3$. Since $G$ does not contain $K_4$, we see that $y_4\notin \left\{x_1,x_2,y_1\right\}$. Now, we observe that $x_{3}x{x}_5{y}_4{y}_2{x}_3$ is the cycle of $G\left[N\left(x_4\right)\right]$. Let $N\left(y_2\right)=\left\{x_3,x_4,y_4,z,y_1\right\}$, then, similarly, we can show that $z\notin \left\{x_1,\dots ,x_5,y_1,y_2,y_3,y_4\right\}$ and $\left\{y_1,y_2,y_3,y_4\right\}\subseteq N\left(z\right)$. Let $N\left(z\right)=\left\{y_1,y_2,y_3,y_4,w\right\}$, and then $w\notin \left\{x_1,\dots ,x_5,y_1,y_2,y_3,y_4\right\}$ and $N\left(w\right)=\left\{y_1,x_1,x_5,y_4,z\right\}$. It follows that $G$ is icosahedron.

4. Proof of Theorem 5

Since $G$ is 5-regular, we see that $\left|V\left(G\right)\right|$ is even. If $G$ has a contractible edge, then we are done. Therefore, in the rest of the paper, we may assume that $G$ is a contraction-critical 5-connected graph. Hence, by Theorem 1, we can assume that $\left|V\left(G\right)\right|\ge 10$. By Theorem 2, we see that $G$ has type 1, type 2, type 3, or type 4. Next, we complete the proof of Theorem 5 by showing that the following lemmas are true.

Lemma 11.

Let $G$ be a $\text{TCC}$-5-connected-graph. Let $x\in V\left(G\right)$, $abc$ be a path of $G\left[N\left(x\right)\right]$, and $G_0=G/\left\{xa,bc\right\}$. If $G\left[N\left(x\right)-\left\{a,b,c\right\}\right]\cong K_2$, then $\kappa \left(G_0\right)\ge 4$.

Proof.

Suppose $\kappa \left(G_1\right)\le 3$. Let $T_1$ be a smallest separator of $G_1$, and let $A_1$ be a $T_1$-fragment. Clearly, $\left|T_1\right|=3$ and $\left\{\left[xa\right],\left[bc\right]\right\}\subseteq T_1$. Let $T=T_1\cup \left\{x,a,b,c\right\}-\left\{\left[xa\right],\left[bc\right]\right\}$. Clearly, $\left|T\right|=5$ and $\left\{x,a,b,c\right\}\subseteq T$. Furthermore, $A=A_1$ is a fragment of $G$ such that $N\left(A\right)=T$. Since $G\left[N\left(x\right)\right]-\left\{a,b,c\right\}$ is a complete graph, either $N\left(x\right)\cap A=\varnothing$ or $N\left(x\right)\cap \overline{A}=\varnothing$, a contradiction. Hence the lemma holds.

Lemma 12.

Let $G$ be a TCC-5-connected graph such that $\left|V\left(G\right)\right|\ge 10$. If $G$ has type 1, then $G$ can be contracted to a 5-connected $H$ such that $0<\left|V\left(G\right)\right|-\left|V\left(H\right)\right|<3$.

Proof.

By the definition of type 1, we know that $G$ contains $K_4$ as a subgraph. Since $G$ is vertex transitive graph, every vertex of $G$ is contained in some $K_4$. Let $x$ be a vertex of $G$, and let $N\left(x\right)=\left\{x_1,\dots ,x_5\right\}$. Furthermore, without the loss of generality, suppose $G\left[\left\{x,x_1,x_2,x_3\right\}\right]\cong K_4$.

Since $G$ has type 1, we may let $N\left(x_1\right)=\left\{x,x_2,x_3,y_1,w_1\right\}$, $N\left(x_2\right)=\left\{x,x_1,x_3,y_2,w_2\right\}$, and $N\left(x_3\right)=\left\{x,x_1,x_2,y_3,w_3\right\}$. Clearly, $x_4,x_5,y_1,w_1,y_2$, $w_2,y_3$, and $w_3$ are all different to each other since $G$ has type 1.

Let $G_1=G/\left\{x{x}_1,x_2{x}_3\right\}$, and let $G_2=G/\left\{x{x}_2,x_1{x}_3\right\}$. Now, we see that $\delta \left(G_1\right)\ge 5$ and $\delta \left(G_2\right)\ge 5$, since $x_4,x_5,y_1,w_1,y_2,w_2,y_3$, and $w_3$ are all different to each other.

If either $\kappa \left(G_1\right)=5$ or $\kappa \left(G_2\right)=5$, then we are done. So, by Lemma 11, we may assume that $\kappa \left(G_1\right)=4$ and $\kappa \left(G_2\right)=4$. Let $T_1$ be a smallest separator of $G_1$, and let $A_1$ be a $T_1$-fragment. Since $\delta \left(G_1\right)\ge 5$, we see that $\left|A_1\right|\ge 2$ and $\left|\overline{A_1}\right|\ge 2$. Furthermore, we can observe that $T_1\cap \left\{\left[x{x}_1\right],\left[x_2{x}_3\right]\right\}\ne \varnothing$.

Claim 14.

$\left\{\left[x{x}_1\right],\left[x_2{x}_3\right]\right\}-T_1\ne \varnothing$.

Proof.

Suppose $\left\{\left[x{x}_1\right],\left[x_2{x}_3\right]\right\}\subseteq T_1$. Let $T=T_1\cup \left\{x,x_1,x_2,x_3\right\}-\left\{\left[x{x}_1\right],\left[x_2{x}_3\right]\right\}$. It follows that $\left|T\right|=6$ and $\left\{x,x_1,x_2,x_3\right\}\subseteq T$. Furthermore, $G-T=A_1\cup \overline{A_1}$. Recall that $x_4{x}_5\in E\left(G\right)$; then, either $N\left(x\right)\cap A_1=\varnothing$ or $N\left(x\right)\cap \overline{A_1}=\varnothing$. Without loss of generality, we may assume that $N\left(x\right)\cap A_1=\varnothing$. Then, $A=A_1$ is a fragment of $G$ such $N\left(A\right)=T-\left\{x\right\}$. It follows that $\left|\overline{A}\right|\ge \left|\overline{A_1}\right|+1\ge 3$. Since $N\left(x_1\right)\cap A\ne \varnothing$, we see that $\left\{y_1,w_1\right\}\subseteq A\cup N\left(A\right)$. It follows that $N\left(x_1\right)\cap \overline{A}=\left\{x\right\}$. Similarly, $N\left(x_2\right)\cap \overline{A}=\left\{x\right\}$. Hence, $N\left(\left\{x_1,x_2\right\}\right)\cap \overline{A}=\left\{x\right\}$. Now, Lemma 2 assures us that $\left|\overline{A}\right|=1$, a contradiction.

By Claim 14, without the loss of generality, let $\left[x_2{x}_3\right]\in T_1$ and $\left[x{x}_1\right]\in A$.

Let $T=T_1\cup \left\{x_2,x_3\right\}-\left\{\left[x_2{x}_3\right]\right\}$, and then, $\left|T\right|=5$ and $\left\{x_2,x_3\right\}\subseteq T$. Furthermore, $A=\left(A_1-\left[x{x}_1\right]\right)\cup \left\{x,x_1\right\}$ is a $T$-fragment and $\overline{A}={\overline{A}}_1$. Clearly, $\left|A\right|\ge 3$ and $\left|\overline{A}\right|\ge 2$.

Similarly, we may assume $G$ has a fragment $B$ such that $\left\{x,x_2\right\}\subseteq B$ and $\left\{x_1,x_3\right\}\subseteq N\left(B\right)$. Furthermore, we may assume that $\left|B\right|\ge 3$ and $\left|\overline{B}\right|\ge 2$.

Focusing on $A$ and $B$, we see that $x\in A\cap B$, $x_2\in N\left(A\right)\cap B$, $x_1\in N\left(B\right)\cap A$, and $x_3\in N\left(A\right)\cap N\left(B\right)$. If $N\left(x_3\right)\cap \left(B\cap \overline{A}\right)\ne \varnothing$, then, since $y_3{w}_3\in E\left(G\right)$, we see that $N\left(x_3\right)\cap \overline{B}=\varnothing$, a contradiction. Hence, we may assume $N\left(x_3\right)\cap \left(B\cap \overline{A}\right)=\varnothing$. By symmetry, let $N\left(x_3\right)\cap \left(A\cap \overline{B}\right)=\varnothing$.

Claim 15.

$B\cap \overline{A}=\varnothing$ and $\overline{B}\cap A=\varnothing$.

Proof.

Suppose $B\cap \overline{A}\ne \varnothing$. Since $N\left(x_3\right)\cap \left(B\cap \overline{A}\right)=\varnothing$, Lemma 1 assures us that $\overline{B}\cap A=\varnothing$ and $\left|N\left(A\right)\cap B\right|>\left|N\left(B\right)\cap A\right|$. If $\overline{B}\cap \overline{A}\ne \varnothing$, then $A\cap B$ is a fragment. On the other hand, we find that $N\left(x_1\right)\cap A\cap B=N\left(x_3\right)\cap A\cap B=\left\{x\right\}$. Now, Lemma 2 assures us that $A\cap B=\left\{x\right\}$ and $\left|N\left(B\right)\cap A\right|\ge 2$. Thus, $\left|N\left(A\right)\cap B\right|\ge \left|N\left(B\right)\cap A\right|+1\ge 2+1=3$. It follows that $\left|N\left(A\right)\cap \overline{B}\right|\le 1$. Now, Lemma 1 assures us that $\overline{B}\cap \overline{A}=\varnothing$, a contradiction. Hence, $\overline{B}\cap \overline{A}=\varnothing$. Now, we find that $\overline{B}=\overline{B}\cap N\left(A\right)$. This implies that $\left|\overline{B}\cap N\left(A\right)\right|=\left|\overline{B}\right|\ge 2$. Since $A\cap B\ne \varnothing$ and $B\cap \overline{A}\ne \varnothing$, Lemma 1 implies that $\left|N\left(B\right)\cap A\right|\ge 2$ and $\left|N\left(B\right)\cap \overline{A}\right|\ge 2$. Hence, we see that $\left|N\left(B\right)\cap A\right|=\left|N\left(B\right)\cap \overline{A}\right|=2$, which implies that $\left(B\cap \overline{A}\right)$ is a fragment of $G$. It follows that $N\left(x_3\right)\cap \left(B\cap \overline{A}\right)\ne \varnothing$, a contradiction. Hence, we have $B\cap \overline{A}=\varnothing$, and, similarly, $\overline{B}\cap A=\varnothing$.

If $\overline{B}\cap \overline{A}\ne \varnothing$, then Lemma 1 assures us that $A\cap B$ is a fragment of $G$. Since every vertex of $G$ has type 1, we see that $N\left(x_1\right)\cap A\cap B=N\left(x_3\right)\cap A\cap B=\left\{x\right\}$. Now, Lemma 2 assure us that $A\cap B=\left\{x\right\}$. This implies that $\left|N\left(B\right)\cap A\right|\ge 2$ and $\left|N\left(A\right)\cap B\right|\ge 2$. Now, Lemma 1 assures us that $\left|N\left(B\right)\cap A\right|=\left|N\left(A\right)\cap \overline{B}\right|=\left|N\left(A\right)\cap B\right|=\left|N\left(B\right)\cap \overline{A}\right|=2$. Thus, we may assume that $N\left(B\right)\cap A=\left\{x_1,x_4\right\},N\left(A\right)\cap \overline{B}=\left\{y_1,w_1\right\},N\left(A\right)\cap B=\left\{x_2,x_5\right\},\text{\hspace{0.17em}and\hspace{0.17em}}N\left(B\right)\cap \overline{A}=\left\{y_1,w_2\right\}$. Since $\left\{x_1,x_2,x_3\right\}\cap N\left(x_5\right)=\varnothing$, we see that $d\left(x_5\right)=4$, a contradiction. Hence, we may assume that $\overline{B}\cap \overline{A}=\varnothing$. It follows that $\overline{B}=\overline{B}\cap N\left(A\right)$ and $\overline{A}=\overline{A}\cap N\left(B\right)$. Furthermore, $\left|\overline{B}\cap N\left(A\right)\right|=\left|\overline{B}\right|\ge 2$ and $\left|\overline{A}\cap N\left(B\right)\right|=\left|\overline{A}\right|\ge 2$. Now, Lemma 1 assures us that $\left|N\left(B\right)\cap A\right|=\left|N\left(A\right)\cap \overline{B}\right|=\left|N\left(A\right)\cap B\right|=\left|N\left(B\right)\cap \overline{A}\right|=2$. Hence, we see that $A\cap B$ is a fragment of $G$. Now, similarly, we see that $d\left(x_4\right)=4$, a contradiction. Hence, we see that either $\kappa \left(G_1\right)\ge 5$ or $\kappa \left(G_2\right)\ge 5$.

Lemma 13.

Let $G$ be a $\text{TCC}$-5-connected graph such that $\left|V\left(G\right)\right|\ge 10$. If $G$ has type 3, then $G$ can be contracted to a 5-connected $H$ such that $0<\left|V\left(G\right)\right|-\left|V\left(H\right)\right|<3$.

Proof.

Clearly, $G$ does not contain $K_4$. Suppose $G$ has a fragment of cardinality two, say $A=\left\{x,y\right\}$. Since $G$ is 5-regular, we see that $\left|N\left(x\right)\cap N\left(y\right)\right|=3$. Hence, we see that $\mathrm{\Delta }\left(G\left[N\left(y\right)\right]\right)\ge 3$. This contradicts Lemma 8. Hence, every fragment of $G$ contains either one vertex or at least three vertices. Let $x$ be a vertex of $G$ such that $N\left(x\right)=\left\{x_1,\dots ,x_5\right\}$. Let $x_1{x}_2{x}_3$ be a path of $G\left[N\left(x\right)\right]$. Furthermore, let $N\left(x_1\right)=\left\{x,x_2,y_1,y_2,y_3\right\}$, $N\left(x_2\right)=\left\{x,x_1,x_3,w_1,w_2\right\}$, and $N\left(x_3\right)=\left\{x,x_2,z_1,z_2,z_3\right\}$. Since $G$ has type 3, we see that $\left\{y_1,y_2,y_3\right\}\cap \left\{x_4,x_5,w_1,w_2\right\}=\varnothing$ and $\left\{z_1,z_z,z_3\right\}\cap \left\{x_4,x_5,w_1,w_2\right\}=\varnothing$.

Let $G_1=G/\left\{x{x}_1,x_2{x}_3\right\}$ and $G_2=G/\left\{x{x}_3,x_1{x}_2\right\}$. By Lemma 11, we have $\kappa \left(G_1\right)\ge 4$ and $\kappa \left(G_2\right)\ge 4$. If either $G_1$ or $G_2$ is 5-connected, then we are done. So we may assume $\kappa \left(G_1\right)=4$ and $\kappa \left(G_2\right)=4$.

Clearly, $\delta \left(G_1\right)\ge 5$ and $\delta \left(G_2\right)\ge 5$. For $i\in \left\{\mathrm{1,2}\right\}$, let $T_i$ be a smallest separator of $G_i$ and $A_i$ be a $T_i$-fragment. Since $\delta \left(G_1\right)\ge 5$ and $\delta \left(G_2\right)\ge 5$, we see that every component of $G-T_i$ has at least two vertices, where $i\in \left\{\mathrm{1,2}\right\}$. Furthermore, $T_1\cap \left\{\left[x{x}_1\right],\left[x_2{x}_3\right]\right\}\ne \varnothing$ and $T_2\cap \left\{\left[x{x}_3\right],\left[x_1{x}_2\right]\right\}\ne \varnothing$. Let $T_i^{\prime }=\left(T_i\cup {\displaystyle {\cup }_{\left[ab\right]\in T_i}\left\{a,b\right\}}\right)-{\displaystyle {\cup }_{\left[ab\right]\in T_i}\left\{\left[a,b\right]\right\}}$, where $i\in \left\{\mathrm{1,2}\right\}$. It follows that $T_i^{\prime }\cap \left\{x_1,x,x_2,x_3\right\}\ne \varnothing$, $i\in \left\{\mathrm{1,2}\right\}$. Clearly, either $\left|T_i^{\prime }\cap \left\{x_1,x,x_2,x_3\right\}\right|=2$ or $\left|T_i^{\prime }\cap \left\{x_1,x,x_2,x_3\right\}\right|=4$, $i\in \left\{\mathrm{1,2}\right\}$.

Claim 16.

For a smallest separator $T$ of $G$, the following holds.

(1)

$\left\{x,x_1,x_2\right\}-T\ne \varnothing$ and $\left\{x,x_2,x_3\right\}-T\ne \varnothing$

(2)

If either $\left\{x_1,x_2,x_3\right\}\subseteq T$ or $\left\{x_1,x,x_3\right\}\subseteq T$, then one component of $G-T$ has exactly one vertex

Proof.

(1)

By symmetry, we only show that $\left\{x,x_1,x_2\right\}-T\ne \varnothing$, and the other one can be handled similarly. Suppose $\left\{x,x_1,x_2\right\}-T\ne \varnothing$, which implies that $\left\{x,x_1,x_2\right\}\subseteq T$. Let $A$ be a $T$-fragment. Since $G\left[N\left(x\right)\right]-\left\{x_1,x_2,x_3\right\}\cong K_2$, we see that $x_3\notin T$. Hence, without the loss of generality, let $x_3\in A$. Notice the fact that $x_1{x}_3\notin E\left(G\right)$, and we see that $A$ has at least two vertices. Now, the fact that $G\left[N\left(x\right)\right]-\left\{x_1,x_2,x_3\right\}\cong K_2$ assure us that $N\left(x\right)\cap A=\left\{x_3\right\}$. Similarly, we have $N\left(x_2\right)\cap A=\left\{x_3\right\}$. Hence, $N\left(\left\{x,x_2\right\}\right)\cap A=\left\{x_3\right\}$. Now Lemma 2 assures us that $A=\left\{x_3\right\}$, a contradiction.

(2)

Suppose $\left\{x_1,x_2,x_3\right\}\subseteq T$. Furthermore, suppose every component of $G-T$ has at least two vertices. Let $A$ be a fragment of $T$. Since $G\left[N\left(x\right)\right]-\left\{x_1,x_2,x_3\right\}\cong K_2$, we see that $x\notin T$ . Without the loss of generality, let $x\in A$. Since both $A$ and $\overline{A}$ have at least two vertices, it follows that $A$ and $\overline{A}$ have at least three vertices.

Notice that $N\left(x_2\right)\cap A=\left\{x\right\}$. If $\left|N\left(x_1\right)\cap A\right|=1$, then $N\left(\left\{x_2,x_1\right\}\right)\cap A=\left\{x\right\}$. Now, Lemma 2 assures us that $A=\left\{x\right\}$, a contradiction. So, we may assume that $\left|N\left(x_1\right)\cap A\right|\ge 2$. Similarly, we see that $\left|N\left(x_3\right)\cap A\right|\ge 2$. Since $\left|N\left(x_1\right)\cap A\right|\ge 2$, we see that $y_2\in N\left(A\right)$. Hence, by symmetry, we may assume $y_1\in A$ and $y_3\in \overline{A}$. It follows that $N\left(x_1\right)\cap A=\left\{x,y_1\right\}$ and $N\left(x_1\right)\cap \overline{A}=\left\{y_3\right\}$. Thus, Lemma 4 assures us that $y_2\in \text{Ad}\left(x_1,\overline{A}\right)$. Now, we see that $N\left(y_2\right)\cap A=\left\{y_1\right\}$, since $G\left[N\left(y_2\right)\right]-\left\{y_1,x_1,y_3\right\}\cong K_2$. Notice that $N\left(\left\{x_1,x_2,y_2\right\}\right)\cap A=\left\{x,y_1\right\}$, and Lemma 2 assures us that $A=\left\{x,y_1\right\}$, a contradiction. Hence, we see that one component of $G-T$ has exactly one vertex. Similarly, we see that the fact $\left\{x_1,x,x_3\right\}\subseteq T$ assures us that one component of $G-T$ has exactly one vertex.

Claim 17.

$\left\{x_1,x,x_2,x_3\right\}-T_i^{\prime }\ne \varnothing$, $i\in \left\{\mathrm{1,2}\right\}$.

Proof.

We only show that $\left\{x_1,x,x_2,x_3\right\}-T_1^{\prime }\ne \varnothing$, and the other one can be handled similarly. Suppose $\left\{x_1,x,x_2,x_3\right\}\subseteq T_1^{\prime }$. It follows that $\left|T_1^{\prime }\right|=6$. Let $A\prime$ be a component of $G-T_1^{\prime }$, $\overline{A\prime }=G-T_1^{\prime }-A\prime$. As $x_4{x}_5\in E\left(G\right)$, it follows that either $N\left(x\right)\cap A\prime =\varnothing$ or $N\left(x\right)\cap \overline{A^{\prime }}=\varnothing$. Similarly, we see that either $N\left(x_2\right)\cap A\prime =\varnothing$ or $N\left(x_2\right)\cap \overline{A^{\prime }}=\varnothing$. Without the loss of generality, let $N\left(x\right)\cap A\prime =\varnothing$. It follows that $N\left(x_2\right)\cap \overline{A^{\prime }}=\varnothing$, $N\left(x_2\right)\cap A\prime \ne \varnothing$, and $N\left(x\right)\cap \overline{A^{\prime }}\ne \varnothing$.

It follows that $T_1^{\prime }-\left\{x\right\}$ is a smallest separator of $G$. Let $T=T_1^{\prime }-\left\{x\right\}$, and $A=A\prime$ is a $T-$ fragment such that $\overline{A}=\overline{A^{\prime }}\cup \left\{x\right\}$. If $\left|A\right|=1$, then either $A=\left\{w_1\right\}$ or $A=\left\{w_2\right\}$. It follows that $N\left(x_1\right)\cap \left\{w_1,w_2\right\}\ne \varnothing$, a contradiction. Hence, we have $\left|A\right|\ge 3$. Notice that $\overline{A}=\overline{A^{\prime }}\cup \left\{x\right\}$, and we see that $\left|\overline{A}\right|\ne 1$. It follows that $\left|\overline{A}\right|\ge 3$.

Hence, we see that $T$ is a smallest separator of $G$ such that $T\cap \left\{x_1,x,x_2,x_3\right\}=\left\{x_1,x_2,x_3\right\}$, but both $A$ and $\overline{A}$ have cardinality at least two, which contradicts Claim 16.

By Claim 17, without the loss of generality, we may assume that $T_1^{\prime }\cap \left\{x_1,x,x_2,x_3\right\}=\left\{x_1,x\right\}$. It follows that $\left|T_1^{\prime }\right|=5$. Let $B_1$ be a $T_1^{\prime }$-fragment. Without the loss of generality, let $\left\{x_2,x_3\right\}\subseteq B_1$. On the other hand, by Claim 17, either $T_2^{\prime }\cap \left\{x_1,x,x_2,x_3\right\}=\left\{x_1,x_2\right\}$ or $T_2^{\prime }\cap \left\{x_1,x,x_2,x_3\right\}=\left\{x,x_3\right\}$. Furthermore, since every component of $G-T_i$ has at least two vertices, we see that every component of $G-T_i^{\prime }$ has at least two vertices, where $i\in \left\{\mathrm{1,2}\right\}$. This implies that every component of $G-T_i^{\prime }$ has at least three vertices for each $i=\mathrm{1,2}$. We will complete the proof of the lemma according the following two cases.

Case 1.

$T_2^{\prime }\cap \left\{x_1,x,x_2,x_3\right\}=\left\{x_3,x\right\}$.

It follows that $\left|T_2^{\prime }\right|=5$. Let $B_2$ be a $T_2^{\prime }$-fragment. Without the loss of generality, suppose $\left\{x_1,x_2\right\}\subseteq B_2$.

Now, we see that $x_2\in B_1\cap B_2$, $x_1\in T_1^{\prime }\cap B_2$, $x_3\in T_2^{\prime }\cap B_1$, and $x\in T_1^{\prime }\cap T_2^{\prime }$.

Claim 18.

${\overline{B}}_1\cap {\overline{B}}_2\ne \varnothing$.

Proof.

Otherwise, assume that ${\overline{B}}_1\cap {\overline{B}}_2=\varnothing$. Notice that $N\left(x\right)\cap {\overline{B}}_1\ne \varnothing$ and $N\left(x\right)\cap {\overline{B}}_2\ne \varnothing$, and we see that $N\left(x\right)\cap {\overline{B}}_1\cap T_2^{\prime }\ne \varnothing$ and $N\left(x\right)\cap {\overline{B}}_2\cap T_1^{\prime }\ne \varnothing$ since $G\left[N\left(x\right)\right]-\left\{x_1,x_2,x_3\right\}\cong K_2$. Without the loss of generality, let $x_4\in {\overline{B}}_2\cap T_1^{\prime }$. Furthermore, we see that $N\left(x\right)\cap {\overline{B}}_1\cap B_2=\varnothing$ and $N\left(x\right)\cap {\overline{B}}_2\cap B_1=\varnothing$. If $B_1\cap {\overline{B}}_2\ne \varnothing$, then Lemma 1 assures us that ${\overline{B}}_1\cap B_2=\varnothing$. It follows that $\left|{\overline{B}}_1\cap T_2^{\prime }\right|\ge \left|{\overline{B}}_1\right|\ge 3$. Now, Lemma 1 assures us that $\left|{\overline{B}}_2\cap T_1^{\prime }\right|\ge \left|{\overline{B}}_1\cap T_2^{\prime }\right|\ge 3$ and $\left|B_2\cap T_1^{\prime }\right|\ge \left|{\overline{B}}_1\cap T_2^{\prime }\right|\ge 3$. This implies that $\left|T_1^{\prime }\right|\ge 6$, a contradiction.

Thus, we may assume that $B_1\cap {\overline{B}}_2=\varnothing$ and, similarly, ${\overline{B}}_1\cap B_2=\varnothing$. Similar to the argument of the last paragraph, we have $\left|{\overline{B}}_1\right|\ge 3$ and $\left|{\overline{B}}_2\right|\ge 3$. It follows that $\left|B_2\cap T_1^{\prime }\right|\ge \left|{\overline{B}}_1\cap T_2^{\prime }\right|\ge 3$ and $\left|{\overline{B}}_2\cap T_1^{\prime }\right|\ge \left|{\overline{B}}_1\cap T_2^{\prime }\right|\ge 3$. Hence, $\left|T_1^{\prime }\right|\ge 6$, a contradiction. Hence, Claim 18 holds.

By Claim 18 and Lemma 1, we see that $B_1\cap B_2$ is a fragment and $N\left(B_1\cap B_2\right)\cap \left\{x_1,x,x_2,x_3\right\}=\left\{x_1,x,x_3\right\}$. Now, Claim 16 implies that $B_1\cap B_2=\left\{x_2\right\}$. Therefore, $\left\{w_1,w_2\right\}\subseteq B_1\cup T_1^{\prime }$. If $\left|B_1\cup T_1^{\prime }\right|\le 8$, it follows that $N\left(x_3\right)\subseteq B_1\cup T_1^{\prime }-\left\{x_4,x_1,y_1,y_2\right\}$, which implies that $d\left(x_3\right)\le 4$, a contradiction. So, we may assume that $\left|B_1\cup T_1^{\prime }\right|\ge 9$. Similarly, we may assume that $\left|B_2\cup T_2^{\prime }\right|\ge 9$.

Claim 19.

$B_1\cap {\overline{B}}_2=\varnothing$ and $B_2\cap {\overline{B}}_1=\varnothing$.

Proof.

Clearly, ${\overline{B}}_1\cap {\overline{B}}_2$ is a fragment. It follows that $N\left(x\right)\cap {\overline{B}}_1\cap {\overline{B}}_2\ne \varnothing$. Hence, $N\left(x\right)\cap {\overline{B}}_1\cap B_2=\varnothing$ and $N\left(x\right)\cap {\overline{B}}_2\cap B_1=\varnothing$, since $G\left[N\left(x\right)\right]-\left\{x_1,x_2,x_3\right\}\cong K_2$.

Now, if $B_1\cap {\overline{B}}_2\ne \varnothing$, then the fact $N\left(x\right)\cap {\overline{B}}_1\cap B_2=\varnothing$ assures us that $B_2\cap {\overline{B}}_1=\varnothing$. Notice that $\left|B_2\cup T_2^{\prime }\right|\ge 9$ and $B_1\cap B_2=\left\{x_2\right\}$, and we have $\left|B_2\cap T_1^{\prime }\right|\ge 3$.

Now, Lemma 1 assures us that $\left|B_1\cap T_2^{\prime }\right|\ge \left|B_2\cap T_1^{\prime }\right|\ge 3$ and $\left|{\overline{B}}_1\cap T_2^{\prime }\right|\ge \left|B_2\cap T_1^{\prime }\right|\ge 3$. Hence, $\left|T_2^{\prime }\right|\ge 6$, a contradiction. This contradiction implies that $B_1\cap {\overline{B}}_2=\varnothing$. Similarly, $B_2\cap {\overline{B}}_1=\varnothing$.

Now, we are ready to complete the proof of Case 1. Notice that $\left|B_2\cup T_2^{\prime }\right|\ge 9$, $B_1\cap B_2=\left\{x_2\right\}$, and $B_2\cap {\overline{B}}_1=\varnothing$, and we see that $\left|B_2\cap T_1^{\prime }|\ge 3\right.$. Similarly, $\left|B_1\cap T_2^{\prime }|\ge 3\right.$. Now, Lemma 1 assures us that $\left|{\overline{B}}_1\cap T_2^{\prime }\right|\ge \left|B_2\cap T_1^{\prime }\right|\ge 3$. It follows that $\left|T_2^{\prime }\right|\ge 6$, a contradiction.

Case 2.

$T_2^{\prime }\cap \left\{x_1,x,x_2,x_3\right\}=\left\{x_1,x_2\right\}$.

It follows that $\left|T_2^{\prime }\right|=5$. Let $B_2$ be a $T_2^{\prime }$-fragment. Without the loss of generality, suppose $\left\{x,x_3\right\}\subseteq B_2$. Now, we see that $x_3\in B_1\cap B_2$, $x\in T_1^{\prime }\cap B_2$, $x_2\in T_2^{\prime }\cap B_1$, and $x_1\in T_1^{\prime }\cap T_2^{\prime }$.

Claim 20.

${\overline{B}}_1\cap {\overline{B}}_2\ne \varnothing$.

Proof.

Suppose ${\overline{B}}_1\cap {\overline{B}}_2=\varnothing$. If $B_1\cap {\overline{B}}_2=\varnothing$, then $\left|{\overline{B}}_2\cap T_1^{\prime }\right|=\left|{\overline{B}}_2\right|\ge 3$. Now, Lemma 1 assures us that $\left|B_1\cap T_2^{\prime }\right|\ge \left|{\overline{B}}_2\cap T_1^{\prime }\right|\ge 3$. This implies that $\left|{\overline{B}}_1\cap T_2^{\prime }\right|\le 2$, which implies that $\left|{\overline{B}}_1\cap T_2^{\prime }\right|\ge \left|{\overline{B}}_2\cap T_1^{\prime }\right|$. Now, Lemma 1 assures us that ${\overline{B}}_1\cap B_2=\varnothing$, which implies that $\left|{\overline{B}}_1\right|\le 2$, a contradiction.

Thus, we may assume that $B_1\cap {\overline{B}}_2\ne \varnothing$. Similarly, ${\overline{B}}_1\cap B_2\ne \varnothing$. Thus, both $B_1\cap {\overline{B}}_2$ and ${\overline{B}}_1\cap B_2$ are fragments of $G$. Without loss of generality, we may assume $y_1\in B_1\cap {\overline{B}}_2$. Therefore, $y_3\in {\overline{B}}_1\cap B_2$ and $y_2\in T_1^{\prime }\cap T_2^{\prime }$. Notice that $G\left[N\left(y_2\right)\right]-\left\{x_1,y_1,y_3\right\}\cong K_2$, and then either $\left|N\left(y_2\right)\cap B_1\cap {\overline{B}}_2\right|=1$ or $\left|N\left(y_2\right)\cap {\overline{B}}_1\cap B_2\right|=1$. Without the loss of generality, let $\left|N\left(y_2\right)\cap B_1\cap {\overline{B}}_2\right|=1$. Now, we find that $N\left(\left\{x_1,y_2\right\}\right)\cap B_1\cap {\overline{B}}_2=\left\{y_1\right\}$. Now, Lemma 2 assures us that $B_1\cap {\overline{B}}_2=\left\{y_1\right\}$. Thus, $y_1{x}_2\in E\left(G\right)$. This contradicts the fact that $G$ has type 3.

Now, we are ready to complete the proof of Case 2. By Claim 20, we have that $B_1\cap B_2$ is a fragment, and $N\left(B_1\cap B_2\right)\cap \left\{x_1,x,x_2,x_3\right\}=\left\{x,x_1,x_2\right\}$. This contradicts Claim 16.

Lemma 14.

Let $G$ be a TCC-5-connected graph such that $\left|V\left(G\right)\right|\ge 10$. If $G$ has type 4, then $G$ can be reduced to a 5-connected $H$ such that $0<\left|V\left(G\right)\right|-\left|V\left(H\right)\right|<3$.

Proof.

Let $x$ be a vertex of $G$ such that $N\left(x\right)=\left\{x_1,\dots ,x_5\right\}$. Let $x_1{x}_2{x}_3{x}_4{x}_5$ be a path of $G$. Now, Lemma 10 assures us that $G$ does not contain $K_4$. By Lemma 9, every fragment of $G$ has cardinality one or at least four.

Claim 21.

Either $N\left(x_2\right)\cap N\left(x_3\right)=\left\{x\right\}$ or $N\left(x_3\right)\cap N\left(x_4\right)=\left\{x\right\}$.

Proof.

Suppose $\left|N\left(x_2\right)\cap N\left(x_3\right)\right|\ge 2$ and $\left|N\left(x_3\right)\cap N\left(x_4\right)\right|\ge 2$. Let $N\left(x_3\right)=\left\{z_1,z_2,x_4,x,x_2\right\}$ and $N\left(x_2\right)=\left\{w_1,x_1,x,x_2,z_1\right\}$, where $z_2{x}_4\in E\left(G\right)$. If $w_1{x}_1\notin E\left(G\right)$, then $G\left[N\left(x_1\right)\right]$ has at least two components, a contradiction. Thus, $w_1{x}_1\in E\left(G\right)$. Let $N\left(x_1\right)=\left\{t_1,t_2,w_1,x_2,x\right\}$. We may assume $t_1{t}_2{w}_1{x}_{2}x$ is the path of $G\left[N\left(x_1\right)\right]$. Now, we see that $N\left(x_2\right)\cap N\left(w_1\right)=\left\{x_1\right\}$. Let $g\in \text{Aut}\left(G\right)$ such that $g\left(x\right)=x_1$. It follows that ${\left.g\right|}_{N\left(x\right)}$ is a map from $N\left(x\right)$ to $N\left(x_1\right)$. It follows that either $g\left(x_1\right)=x$ or $g\left(x_1\right)=t_1$.

If $g\left(x_1\right)=x$, then $g\left(x_2\right)=x_2,g\left(x_3\right)=w_1,g\left(x_4\right)=t_2,\text{\hspace{0.17em}and\hspace{0.17em}}g\left(x_5\right)=t_1$. Now, since $\left|N\left(x_2\right)\cap N\left(x_3\right)\right|\ge 2$, we see that $\left|N\left(x_2\right)\cap N\left(w_1\right)\right|\ge 2$, a contradiction. So, we may assume that $g\left(x_1\right)=t_1$. It follows that $g\left(x_2\right)=t_2,g\left(x_3\right)=w_1,g\left(x_4\right)=x_2,g\left(x_5\right)=x_1$. Now, since $\left|N\left(x_3\right)\cap N\left(x_4\right)\right|\ge 2$, we see that $\left|N\left(x_2\right)\cap N\left(w_1\right)\right|\ge 2$, a contradiction.

Now, by symmetry, assume that $N\left(x_2\right)\cap N\left(x_3\right)=\left\{x\right\}$. Let $N\left(x_2\right)=\left\{y_1,y_2,x_1,x,x_3\right\}$ and $N\left(x_3\right)=\left\{z_1,z_2,x_4,x,x_2\right\}$. Furthermore, let $y_1{y}_2{x}_{1}x{x}_3$ and $z_1{z}_2{x}_{4}x{x}_2$ be the paths of $G\left[N\left(x_2\right)\right]$ and $G\left[N\left(x_3\right)\right]$, respectively. Hence, we may let $N\left(x_1\right)=\left\{w_1,w_2,y_2,x_2,x\right\}$, and $w_1{w}_2{y}_2{x}_{2}x$ is the path of $G\left[N\left(x_1\right)\right]$. Furthermore, we have $\left|N\left(x_2\right)\cap N\left(x_3\right)\right|=1$ and $\left|N\left(x_3\right)\cap N\left(x_4\right)\right|=2$.

Let $G_0=G/\left\{x{x}_1,x_2{x}_3\right\}$. Lemma 11 assures us that $\kappa \left(G_0\right)\ge 4$. Suppose $\kappa \left(G_0\right)=4$. Let $T^{\prime }$ be a smallest separator of $G_0$. Clearly, we observe that $\left\{\left[x{x}_1\right],\left[x_2{x}_3\right]\right\}\cap T^{\prime }\ne \varnothing$.

Claim 22.

$\left\{\left[x{x}_1\right],\left[x_2{x}_3\right]\right\}\subseteq T^{\prime }$.

Proof.

Suppose $\left[x{x}_1\right]\notin T^{\prime }$. Let $T_0=T^{\prime }\cup \left\{x_2,x_3\right\}-\left\{\left[x_2{x}_3\right]\right\}$. Then, $T_0$ is a smallest separator of $G$. Let $A$ be a fragment of $T_0$ which contains $\left\{x,x_1\right\}$. It follows that $\left|A\right|\ge 2$. Now, Lemma 9 shows that $\left|\overline{A}\right|=1$. Clearly, $\overline{A}\subseteq \left\{N\left(x_2\right)\cap N\left(x_3\right)\right\}$. Now, since $x\in A$, we see that $\left|N\left(x_2\right)\cap N\left(x_3\right)\right|=2$, which is a contradiction. Hence, we may assume that $\left[x{x}_1\right]\in T^{\prime }$. If $\left[x_2{x}_3\right]\notin T^{\prime }$, let $T_0=T^{\prime }\cup \left\{x,x_1\right\}-\left\{\left[x{x}_1\right]\right\}$. Then, $T_0$ is smallest separator $G$. Let $B$ be a $T_0$-fragment which contains $\left\{x_2,x_3\right\}$. It follows that $\left|B\right|\ge 2$. Now, Lemma 9 shows that $\left|\overline{B}\right|=1$. Clearly, $\overline{B}\subseteq \left\{x_4,x_5\right\}$. Hence, $x_1$ is adjacent to either $x_4$ or $x_5$, a contradiction. Hence, $\left[x_2{x}_3\right]\in T^{\prime }$.

Let $T_0=T^{\prime }\cup \left\{x,x_1,x_2,x_3\right\}-\left\{\left[x{x}_1\right],\left[x_2{x}_3\right]\right\}$. Let $A$ be a component of $G-T_0$, $A^{\prime }=G-T_0-A$. As $x_4{x}_5\in E\left(G\right)$, $N\left(x\right)\cap A=\varnothing$ or $N\left(x\right)\cap A^{\prime }=\varnothing$. Similarly, $N\left(x_2\right)\cap A=\varnothing$ or $N\left(x_2\right)\cap A^{\prime }=\varnothing$. Without the loss of generality, let $N\left(x\right)\cap A=\varnothing$. Then, $N\left(x_2\right)\cap A\prime =\varnothing$ and $N\left(x_2\right)\cap A\ne \varnothing$, $N\left(x\right)\cap A\prime \ne \varnothing$.

Hence, $T=T_0-\left\{x\right\}$ is a smallest separator of $G$. Let $A$ be a $T-$fragment. Clearly, $\overline{A}=A^{\prime }\cup \left\{x\right\}$. This implies that $\left|\overline{A}\right|\ge 2$. Now, Lemma 9 shows that $\left|A\right|=1$. So, $A\subseteq N\left(x_2\right)\cap N\left(x_3\right)$. Recall that $x\in \overline{A}$, and we find that $\left|N\left(x_2\right)\cap N\left(x_3\right)\right|\ge 2$. This contradicts the fact that $N\left(x_2\right)\cap N\left(x_3\right)=\left\{x\right\}$.

Acknowledgments

This work was supported by NSFC (no. 11961051) and Natural Sciences Foundation of Guangxi Province (no. 2018GXNSFAA050117).

References

[1] T. Tutte, "A theory of 3-connected graphs," Indagationes Mathematicae (Proceedings), vol. 64, pp. 441-455, DOI: 10.1016/s1385-7258(61)50045-5, 1961.

[2] C. Thomassen, B. Toft, "Non-separating induced cycles in graphs," Journal of Combintroial Theory, Series B, vol. 31, pp. 199-224, DOI: 10.1016/s0095-8956(81)80025-1, 1981.

[3] M. Kriesell, "How to contract an essentially 6-connected graph to a 5-connected graph," Discrete Mathematics, vol. 307, pp. 494-510, DOI: 10.1016/j.disc.2005.09.040, 2007.

[4] K. Ando, C. Qin, "Some structural properties of minimally contraction-critically 5-connected graphs," Discrete Mathematics, vol. 311, pp. 1084-1097, DOI: 10.1016/j.disc.2010.10.022, 2011.

[5] C. Qin, X. Yuan, J. Su, "Triangles in contraction-critical 5-connected graphs," Asutralasian Journal of Combinatorics, vol. 33, pp. 139-146, 2005.

[6] C. Qin, X. Yuan, J. Su, "Some properties of contraction critical 5-connected graphs," Discrete Mathematics, vol. 308, pp. 5742-5756, DOI: 10.1016/j.disc.2007.10.041, 2008.

[7] M. Kriesell, "Average degree and contractibility," Journal of Graph Theory, vol. 51 no. 3, pp. 205-224, DOI: 10.1002/jgt.20131, 2005.

[8] M. Kriesell, "A survey on contractible edges in graphs of a given vertex connectivity," Graphs and Combinatorics, vol. 18,DOI: 10.1007/s003730200000, 2002.

[9] M. Kriesell, "A degree sum condition for the existence of a contractible edge in a κ -connected graph," Jouranl of Combintroial Theory, Series B, vol. 82, pp. 81-101, DOI: 10.1006/jctb.2000.2024, 2001.

[10] J. Su, "Vertices of degree 5 in contraction- critical 5-connected graphs," Journal of Guangxi Normal University, vol. 3, pp. 12-16, 1997. in Chinese

[11] J. A. Bondy, U. S. R. Murty, Graph Theory with Applications, 1976.

[12] W. Mader, "Generalizations of critical connectivity of graphs," Discrete Mathematics, vol. 72, pp. 267-283, DOI: 10.1016/0012-365x(88)90216-6, 1988.