Printer Friendly

How to Contract a Vertex Transitive 5-Connected Graph.

1. Introduction

All graphs considered here are supposed to be simple, finite, and undirected graphs. For a connected graph G, a subset T c V(G) is called a smallest separator if [absolute value of (T)] = k(G) 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 [greater than or equal to] 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]). iere exists b (k), h (k) such that every k-connected graph G with at least b(k) vertices can be contracted to a k-connected graph [G.sub.0] such that 0 < [absolute value of (V(G))]-[absolute value of (V((G0))] < h(k).

Clearly, Conjecture 1 is true for k [less than or equal to] 4. By Kriesell's examples [3], Conjecture 1 fails for k [greater than or equal to] 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.

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 < [absolute value of (V(G))] - [absolute value of (V(H))] < 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 [member of] V (G), 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[N(x)] [congruent to] [K.sub.2] [union] [K.sub.3]

(ii) Type 2: G[N(x)] [congruent to] [C.sub.5]

(iii) Type 3: G[N(x)] [congruent to] [K.sub.2] [union] [P.sub.2]

(iv) Type 4: G[N(x)] [congruent to] [P.sub.4]

Moreover, for i [member of] {1, 2, 3, 4}, G has type i if every vertex of G has type i.

Furthermore, we need to introduce the graph [G.sup.*] (see Figure 1(e)). One can check that [G.sup.*] is vertex transitive, and [G.sup.*] can be reduced to [K.sub.6] by contracting y[x.sub.1] and x[x.sub.2].

First, we have the following results on the local structure of TCC-5-connected graphs.

Theorem 2. Let G be a TCC-5-connected graph. If [absolute value of (V(G))] [less than or equal to] 9, then either G [congruent to] [K.sub.6] or G [congruent to] [G.sup.*].

Theorem 3. Let G be a TCC-5-connected graph. If [absolute value of (V(G))] [greater than or equal to] 10, then G has type 1, type 2, type 3, or type 4.

Theorem 4. Let G be a 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.sub.6] nor icosahedron, and then, G can be contracted to a 5-connected G' such that 0 < [absolute value of (V(G))]- [absolute value of (V(G'))] < 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 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 = (V(G), E(G)) be a graph, where V(G) denotes the vertex set of G and E(G) denotes the edge set of G. Let Aut(G) denote the automorphism group of G, and let k(G) denote the vertex connectivity of G. Let [P.sub.n] denote a path on n vertices. An edge joining vertices x and y will be written as xy. Let [xy] stand for the new vertex obtained by contracting the edge xy. For x [member of] V(G), we define [N.sub.G] (x) = {x | xy [member of] E(G)}. For F [??] V(G), we define [N.sub.G] (F)= [[union].sub.x[member of]F] [N.sub.G] (x) - F. Furthermore, let G[F] 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 derivative](F) 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 [bar.F] = V(G) - (F [union] T). Clearly, F [not equal to] 0, and [bar.F] is also a T-fragment such that [N.sub.G] (F) = T = [N.sub.G] ([bar.F]). A fragment with least cardinality is called an atom. For [N.sub.G] (x), [d.sub.G] (x), and [N.sub.G] (F), 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 (A). Let x [member of] S, and y [member of] N(x) [intersection] A. A vertex z is said to be an admissible vertex of (x, y; A) if both of the following two conditions hold.

z [member of] N(x) [intersection] N(y) [intersection] S [intersection] [V.sub.5] (G),

[absolute value of (N(z) [intersection] A)] [greater than or equal to] 2. (1)

A vertex z is said to be an admissible vertex of (x; A), if z is an admissible vertex of (x, y; A) for some y [member of] N(x) [intersection] A. Let Ad (x, y; A)(resp. Ad(x; A)) stand for the set of admissible vertices of (x, y; A)(resp. (x; A)). Let e be an edge of G, and a fragment A is said to be a fragment with respect to e if V(e) [??] N(A).

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' be two distinct fragments of G; T = N(F), T' = N(F'). Then, the following statements hold.

(1) If F [intersection] T' [not equal to] 0, then [absolute value of (F [intersection] T')] > [absolute value of ([bar.F]' [intersection] T)], [absolute value of (T' [intersection] T)] > [absolute value of ([bar.F] [intersection] T')]

(2) If F [intersection] T' [not equal to] 0 and F [intersection] T' is not a fragment of G, then [bar.F] [intersection] [bar.F]' = 0 and [absolute value of (F [intersection] T')] > [absolute value of (F' [intersection] T)], [absolute value of (T' [intersection] T)] > [absolute value of (F [intersection] T')]

(3) If F [intersection] T' [not equal to] 0 [not equal to] [bar.F] [intersection] [bar.F]', then both F [intersection] T' and [bar.F] [intersection] [bar.F]' are fragments of G, and N(F [intersection] T') = (T' [intersection] T) [union] (T' [intersection] T) [union] (F [intersection] T')

Lemma 2 (see [4]). Let G be a k-connected graph, and A is a fragment of G. Let B [??] N(A). If [absolute value of (N(B) [intersection] A)] < [absolute value of (B)], then A = N(B) [intersection] 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 [member of] V (G), and A be a fragment such that x [member of] N(A), [absolute value of (A)] [greater than or equal to] 3, and [absolute value of ([bar.A])] [greater than or equal to] 2. If [absolute value of (N(x) [intersection] A)] = 1, then Ad(x; A) [not equal to] 0.

Lemma 5 (see [7]). Let A be a fragment of a contraction-critical 5-connected graph such that [absolute value of (A)] = 2, and let [t.sub.1], [t.sub.2] be two vertices of N (A) such that [absolute value of (N([t.sub.1]) [intersection] A)] = [absolute value of (N([t.sub.2]) [intersection] A)] = 1. Then, either Ad([t.sub.1]; A) [not equal to] 0 or Ad([t.sub.2]; A) [not equal to] 0.

Lemma 6. Let G be a vertex transitive connected graph, and then, for any two vertices x and y, G[N(x)] [congruent to] G[N(y)].

Proof. Since G is a vertex transitive graph, there exist g [member of] Aut(G) such that [x.sup.g] = y. It follows that [(N(x)).sup.g] = N(y). Hence, g[|.sub.N(x)] is an isomorphic of G[N(x)] and G[N(y)], where g[|.sub.N(x)] is the restriction of g on N(x).

Lemma 7. Let p [greater than or equal to] 2 be a prime integer, and let G be a vertex transitive graph with k(G) = p; then, G is a p-regular graph.

Proof. To the contrary, we may assume that [delta](G) > p since [delta](G) [greater than or equal to] k(G). 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 [intersection] B [not equal to] 0. By the definition of atom, A [intersection] B is not a fragment. Lemma 1 assures us that [bar.A] [intersection] [bar.B] = 0 and [absolute value of (A [intersection] N(B))] > [absolute value of ([bar.B] [intersection] N(A))]. This implies that [absolute value of ([bar.A])] > [absolute value of ([bar.B])], a contradiction. Thus, any two atoms of G are disjoint.

Let A and C be two atoms of G such that C [intersection] N(A) [not equal to] 0. It follows that A [intersection] C = 0. We show that C [??] N(A). Otherwise, suppose C [intersection] A [not equal to] 0. If C [intersection] [bar.A] is a fragment of G, then we see that [absolute value of (C [intersection] [bar.A])] < [absolute value of (C)], since C [intersection] N(A) [not equal to] 0. This contradicts the definition of atom. So, C [intersection] A is not a fragment of G. Lemma 1 assures us that A [intersection] [bar.C] = 0 and [absolute value of (C [intersection] N(A))] > [absolute value of (A [intersection] N(C))] = [absolute value of (A)]. It follows that [absolute value of (C)] > [absolute value of (A)], a contradiction. Hence, C [??] N(A). Therefore, N(A) 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 |A| is a subdivision of [absolute value of (N(A)], and hence, [absolute value of (A)] = p. It follows that N[absolute value of (A)] = C. By symmetry, we see that N(C) = A, which implies that [bar.A] = 0, a contradiction.

Lemma 8. Let G be a TCC-5-connected graph. If G does not contain [K.sub.4] as subgraph, then for any x [member of] V(G), [DELTA](G[N(x)]) [less than or equal to] 2.

Proof. Clearly, Lemma 7 assures us that G is 5-regular, which implies that G has an even order. Suppose that x [member of] V(G) with N(x) = {[x.sub.1], ..., [x.sub.5]} such that [x.sub.1] adjacent to at least three vertices of N(x). Let A = {x}, and it follows N (A) = N (x). If G - A - N (A) = 0, then G has six vertices. It follows that G [congruent to] [K.sub.6], which implies G contains [K.sub.4], a contradiction. Hence, we may assume that G - A - N (A) [not equal to] 0. It follows that A is a fragment of G. By symmetry, we assume that {[x.sub.2], [x.sub.3], [x.sub.4]} [??] N([x.sub.1]). Now, we observe that N([x.sub.1]) [intersection] N(A) = {[x.sub.2], [x.sub.3], [x.sub.4]} and [absolute value of (N([x.sub.1]) [intersection] [bar.A])] = 1. Let N([x.sub.1]) [intersection] [bar.A] = {[t.sub.1]}. Let B = {x, [x.sub.1]}, and then N(B) = {[x.sub.2], ..., [x.sub.5], [t.sub.1]}. Now, the fact that [absolute value of (V(G))] is even assures us that G - B - N (B) [not equal to] 0. It follows that B is a fragment of G. Furthermore, we see that N([t.sub.1]) [intersection] B = {[x.sub.1]} and N([x.sub.5]) [intersection] B = {x}. Now, Lemma 5 assures us that either Ad([t.sub.1]; B) [not equal to] 0 or Ad([x.sub.5]; B) [not equal to] 0. If Ad([x.sub.5]; B) [not equal to] 0, then without loss of generality, assume [x.sub.2] [member of] Ad([x.sub.5]; B). Therefore, G[N(x)] is a connected graph. If Ad([t.sub.1]; B) [not equal to] 0, then, similarly, we have that G [N (x)] is a connected graph. Now, since G is vertex transitive, the following claims hold.

Claim 1. For any t [member of] V(G), G[N(t)] is a connected graph.

Claim 2. For any t [member of] V(G), G[N(t)] contains a cycle of length 4.

Proof. Since G is a vertex transitive graph, we only show that N([x.sub.1]) has a cycle of length 4. By Claim 1, we see that for y [member of] N(B), N(y) [intersection] N (B) [not equal to] 0. On the other hand, we observe that G[{[x.sub.2], [x.sub.3], [x.sub.4]}] [congruent to [K.sub.3], since G does not contain [K.sub.4]. This implies that every member of "{[x.sub.2], [x.sub.3], [x.sub.4]} is either adjacent to [t.sub.1] or [x.sub.5]. It follows that [absolute value of (N([t.sub.1]) [intersection] {[x.sub.2], [x.sub.3], [x.sub.4]})] [greater than or equal to] 2 or [absolute value of (N ([x.sub.5]) [intersection] {[x.sub.2], [x.sub.3], [x.sub.4])] [greater than or equal to] 2. By symmetry, we may assume that [absolute value of (N([t.sub.1]) [intersection] {[x.sub.2], [x.sub.3], [x.sub.4]}| [greater than or equal to] 2. It follows that G[N([x.sub.1]] contains a cycle of length 4. Hence, for any t [member of] V(G), G[N(t)] has a cycle of length 4.

Now, we are ready to complete the proof of Lemma 8. By Claim 2, we see that [absolute value of (N ([x.sub.i]) [intersection] N (B))] [greater than or equal to] 2 for i [member of] {2,3,4}. This implies that {[t.sub.1], [x.sub.5]} [??] N([x.sub.2]) [intersection] N([x.sub.3]) [intersection] N([x.sub.4]). Now, we see that every vertex of N (B) is adjacent to exactly one vertex of [bar.A]. If [absolute value of ([bar.B])] = 1, say [bar.B] = {t}, then_G[N(t)] [congruent to] [K.sub.2,3] and G[N([x.sub.2])] [congruent to] [C.sub.5], a contradiction. If [absolute value of ([bar.B])] = 2, we can observe that [bar.B] has a vertex with a degree of at most 4, a contradiction. Hence, we may assume that [absolute value of ([bar.B])] = 3. Now, Lemma 4 shows that Ad ([x.sub.2]; [bar.B]) [not equal to] 0, which implies [absolute value of (N (z) [intersection] [bar.A])] [greater than or equal to] 2 for some z [member of] N(B), a contradiction.

Lemma 9. Let G be a 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 [member of] V(G), [DELTA](G[N(x)]) [less than or equal to] 2.

Claim 3. If A is a fragment of G, then [absolute value of (A)] [not equal to] 2.

Proof. Suppose A = {x,y}. If xy [member of] E(G), then x has three neighbors in G[N(y)], a contradiction. So, we may assume xy [??] E(G). It follows that G[N(A)] [congruent to] [P.sub.5]. Let [x.sub.1][x.sub.2][x.sub.3][x.sub.4][x.sub.5] be the_ path of G[N(A)]. It follows that [absolute value of (N([x.sub.2]) [intersection] [bar.A])] = [absolute value of (N([x.sub.3]) [intersection] [bar.A])] = [absolute value of (N([x.sub.4]) [intersection] [bar.A])] = 1. If [absolute value of ([bar.A])] [greater than or equal to] 3, then Lemma 4 implies that Ad([x.sub.3], [bar.A]) [not equal to] 0. Hence, either [x.sub.2] [member of] Ad([x.sub.3], [bar.A]) or [x.sub.4] [member of] Ad([x.sub.3], [bar.A]). This is a contradiction, since [absolute value of (N([x.sub.2]) [intersection] [bar.A])] = [absolute value of (N([x.sub.4]) [intersection] [bar.A])] = 1. Hence, we may assume that [absolute value of ([bar.A])] [less than or equal to] 2. If [absolute value of ([bar.A])] = 1, then we see that d([x.sub.1]) [less than or equal to] 5, a contradiction. So, we may assume [absolute value of ([bar.A])] = 2. It follows that [absolute value of (V(G))] = 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 [absolute value of (A)] [not equal to] 3.

Proof. We first show that G[A] is a connected graph. Otherwise, let A1 be a component of G[A] such that [A.sub.1] has exactly one vertex. It follows that [A.sub.2] = A - [A.sub.1] is a fragment of cardinality 2, a contradiction. Next, we show that G [A] is a path. Suppose G [A] is a cycle, then a simple calculation shows that [absolute value of ([partial derivative] (A))] = 9. This implies that one vertex of N (A), say w, has exactly one neighbor in A. Now, we find that A - N(w) is a fragment of cardinality 2, a contradiction.

Let xyz be the path of G[A], and let N(A) = {[x.sub.1], ..., [x.sub.5]}. Without the loss of generality, let N(y) = {x, [x.sub.1], [x.sub.2], [x.sub.3], z}.

Subclaim 1. [absolute value of (N(x) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]})] = 2 and [absolute value of (N(z) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]})] = 2.

Proof. Notice that G has type 4; we find that [absolute value of (N(x) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]})] [less than or equal to] 2. If [absolute value of (N(x) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]})] [less than or equal to] 1, then we find that d(x) [less than or equal to] 4, a contradiction. Hence, [absolute value of (N(x) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]})] = 2. By symmetry, [absolute value of (N(z) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]})] = 2.

Without the loss of generality, we may assume that {[x.sub.1], [x.sub.2]} [??] N(x). Now, if {[x.sub.1], [x.sub.2]} [??] N(z), then x[x.sub.1]z[x.sub.2]x is a cycle of G[N(y)], a contradiction. Therefore, {[x.sub.2], [x.sub.3]} [??] N(z), which implies that {[x.sub.4], [x.sub.5]} [??] N(x) [intersection] N(z).

Subclaim 2. G[{[x.sub.1], [x.sub.2], [x.sub.3]}] [congruent to] [bar.[K.sub.3]].

Proof. If [x.sub.1][x.sub.2] [member of] E(G), then N(y) has a triangle, a contradiction. It follows that [x.sub.1][x.sub.2] [??] E(G). Similarly, we have [x.sub.2][x.sub.3] [??] E(G). Furthermore, if [x.sub.1][x.sub.3] [??] E(G), then we find that there is a cycle of length four in N (y), a contradiction. Thus, [x.sub.1][x.sub.3] [??] E(G). It follows that G[{[x.sub.1], [x.sub.2], [x.sub.3]}] [congruent to] [bar.[K.sub.3]].

Now, we are ready to complete the proof of Claim 4. Focusing on [x.sub.2], we find that N([x.sub.2]) [intersection] N(A) [not equal to] 0 since G [N ([x.sub.2])] is connected. By Subclaim 2, we may assume that [x.sub.4] [member of] N([x.sub.2]). Now, we find that there is a cycle of length four in N([x.sub.2]), 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.sub.1], [A.sub.2], and [A.sub.3] be three connected components of G - T.

Subclaim 3. For any y [member of] T, [absolute value of (N(y) [intersection] T)] = 2, and [absolute value of (N(y) [intersection] [A.sub.i])] = 1, i [member of] {1,2,3}.

Proof. Let y [member of] T, let N(y) = {[y.sub.1], ..., [y.sub.5]}. Without the loss of generality, we may assume that [y.sub.i] [member of] [A.sub.i], i [member of] {1,2,3}. Now, we find that N(y) [intersection] T [not equal to] 0, since G has type 4. Suppose [y.sub.4] [member of] N(y) [intersection] T. If N(y) [intersection] T = {[y.sub.4]}, then the fact that G [N(y)] is connected shows that [y.sub.4] has three neighbors in G[N(y)], which contradicts the fact that G has type 4. So, we have N(y) [intersection] T = {[y.sub.4], [y.sub.5]}. It follows that [absolute value of (N(y) [intersection] [A.sub.i])] = 1, i [member of] {1,2,3} and [absolute value of (N(y) [intersection] T)] = 2.

By Subclaim 3, [delta](G[T]) = 2, which implies that G[T] is a

cycle of length 5. Hence, we see that [absolute value of ([A.sub.i])] [not equal to] 1, i [member of] {1,2,3}. Furthermore, by Subclaims 3 and 4, [absolute value of ([A.sub.i])] [not equal to] 3 for each i = 1,2,3. Focusing on A1, we find that [[bar.A].sub.1] = [A.sub.2] [union] [A.sub.3], which implies that [absolute value of ([A.sub.i])] [greater than or equal to] 6. Recall that [absolute value of (N(x) [intersection] [A.sub.1])] = 1, and Lemma 4 shows that Ad(x; [A.sub.1]) [not equal to] 0. Without the loss of generality, assume that y [member of] Ad(x; [A.sub.1]). This implies that [absolute value of (N(y) [intersection] [A.sub.1])] [greater than or equal to] 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 [absolute value of (B)] [greater than or equal to] 2 and [absolute value of ([bar.B])] [greater than or equal to] 2. Let B = {B | B is a fragment such that [absolute value of ([bar.B])] [greater than or equal to] 2 and [absolute value of ([bar.B])] [greater than or equal to] 2}, and let t = min{[absolute value of ([bar.B])] | B [member of] B}. By Claims 3 and 4, we see that t [greater than or equal to] 4. Let [B.sub.1] = {b | B [member of] B and [absolute value of (B)] = t}. Let A [member of] [B.sub.1], and let y [member of] N(A). Now, since G is vertex transitive, every vertex of G is contained in some member of [B.sub.1]. Therefore, there exist B [member of] [B.sub.1] such that y [member of] B. Next, we will analyse the local structure of A and B.

Claim 6. If A [intersection] B [not equal to] 0, then [bar.A] [intersection] [bar.B] [not equal to] 0.

Proof. Suppose A [intersection] B [not equal to] 0 and [bar.A] [intersection] [bar.B] [not equal to] 0. Now, Lemma 1 assures us that [absolute value of (A [intersection] N(B))] [greater than or equal to] [absolute value of (B [intersection] N(A))]. It follows that

[mathematical expression not reproducible]. (2)

This contradicts the choice of A.

Claim 7. A [intersection] [bar.B] [not equal to] 0 if and only if [bar.A] [intersection] B [not equal to] 0.

Proof. Suppose A [intersection] [bar.B] [not equal to] 0. Now, Lemma 1 assures us that [absolute value of (A [intersection] N(B))] [greater than or equal to] [absolute value of (B [intersection] N(A))]. If [bar.A] [intersection] B = 0, then we see that

[mathematical expression not reproducible]. (3)

This contradicts the choice of A. Hence, we see that [bar.A] [intersection] B [not equal to] 0. By symmetry, we see that [bar.A] [intersection] B [not equal to] 0 implies A [intersection] [bar.B] [not equal to] 0.

Claim 8. A [intersection] B = 0.

Proof. Suppose A [intersection] B [not equal to] 0. By Claim 6, we know that [bar.A] [intersection] [bar.B] [not equal to] 0. Hence, A [intersection] B is a fragment of G. By the choice of A, we know that [absolute value of (A [intersection] B)] = 1. Furthermore, since [bar.A] [intersection] [bar.B] [not equal to] 0, Lemma 1 assures us that [absolute value of ([bar.B] [intersection] N(A))] [greater than or equal to] [absolute value of (A [intersection] N(B))].

If A [intersection] [bar.B] = 0, then Claim 7 assures us that [bar.A] [intersection] B = 0. Furthermore, [absolute value of ([bar.A)} = [absolute value of ([bar.B])] [greater than or equal to] 4 implies that [absolute value of (A [intersection] N(B)| = [absolute value of (B [intersection] N(A))] [greater than or equal to] 3. Hence, we find that [absolute value of (N(A))] [greater than or equal to] [absolute value of (B [intersection] N(A))] + [absolute value of ([bar.B] [intersection] N(A))] [greater than or equal to] [absolute value of (B [intersection] N(A))] + [absolute value of (A [intersection] N(B)) [greater than or equal to] 6, a contradiction.

So, we may assume A [intersection] [bar.B] [not equal to] 0. Then, Claim 7 assures us that A [intersection] B [not equal to] 0. Hence, both A [intersection] [bar.B] and B [intersection] [bar.A] are fragments of G. By the choice of A and B, we know that [absolute value of (A [intersection] [bar.B])] = [absolute value of (B [intersection] [bar.A])] = 1. It follows that [absolute value of (A [intersection] N(B))] = [absolute value of (B [intersection] N(A))].

Since [bar.A] [intersection] [bar.B] [not equal to] 0, Lemma 1 assure us that [absolute value of ([bar.B] [intersection] N(A))] [greater than or equal to] [absolute value of (A [intersection] N(B))]. If [absolute value of (A [intersection] N(B))] [greater than or equal to] 3, then [absolute value of (N(A))] [greater than or equal to] [absolute value of (B [intersection] N(A))] + [absolute value of ([bar.B] [intersection] N(A))] [greater than or equal to] 6, a contradiction.

Therefore, let [absolute value of (A [intersection] N(B))] = 2. It_ follows that [absolute value of (A [intersection] N(B))] = [absolute value of (B [intersection] N(A))] = 2. Since [bar.A] [intersection] [bar.B] [not equal to] 0 and A [intersection] B [not equal to] 0, Lemma 1 assures us that [absolute value of ([bar.A] [intersection] N(B))] = [absolute value of ([bar.B] [intersection] N(A))] = 2. This implies that [absolute value of (N(B) [intersection] N(A))] = 1. Let N(B) [intersection] N(A) = {t}. Now, N(t) [intersection] A [intersection] B [not equal to] 0, since A [intersection] B is a fragment. Similarly, we find that N(t) [intersection] A [intersection] [bar.B] [not equal to] 0, N(t) [intersection] [bar.A] [intersection] [bar.B] [not equal to] 0, and N(t) [intersection] [bar.A] [intersection] B [not equal to] 0. Now, we find that G[N(t)] has at least two components, a contradiction.

Claim 9. A [intersection] [bar.B] = 0 and B [intersection] [bar.A] = 0.

Proof. Suppose A [intersection] [bar.B] [not equal to] 0. By Claim 7, we see that [bar.A] [intersection] B [not equal to] 0. Hence, both A [intersection] [bar.B] and [bar.A] [intersection] B are fragments of G. By the choice of A, we see that [absolute value of (A [intersection] [bar.B])] = [absolute value of ([bar.A] [intersection] B)] = 1. It follows that [absolute value of (A [intersection] N(B))] = [absolute value of (B [intersection] N(A))] [greater than or equal to] 3.

If [bar.A] [intersection] [bar.B] [not equal to] 0, then [absolute value of ([bar.B] [intersection] N (A))] [greater than or equal to] [absolute value of ([bar.A] [intersection] N(B))]. Hence, we see that [absolute value of (N(A))] [greater than or equal to] [absolute value of (B [intersection] N(A))] + [absolute value of ([bar.B] [intersection] N(A))] [greater than or equal to] 6, a contradiction.

Hence, we may assume that [bar.A] [intersection] [bar.B] = 0. Then, by the choice of B, we know that [absolute value of ([bar.B])] [greater than or equal to] [absolute value of (B)]. It follows that [absolute value of ([bar.B] [intersection] N(A))] [greater than or equal to] 3. Hence, we find that [absolute value of (N(A))] [greater than or equal to] [absolute value of (B [intersection] N(A))] + [absolute value of ([bar.B] [intersection] N(A))] [greater than or equal to] 6, a contradiction.

Now, we are ready to complete the proof of the Lemma. By Claims 8 and 9, we find that A = A [intersection] N(B) and B = B [intersection] N(A). Now, we find that |B [intersection] N(A))] [less than or equal to] [absolute value of (N(A))] - [absolute value of (B [intersection] N(A))] [less than or equal to] 1, since [absolute value of (B [intersection] N(A))] = [absolute value of (B)] [greater than or equal to] 4. It follows that [absolute value of ([bar.B] [intersection] N(A))] < [absolute value of (A [intersection] N(B))]. Now, Lemma 1 implies that [bar.A] [intersection] [bar.B] = 0. It follows that [absolute value of ([bar.B])] = [absolute value of ([bar.B] [intersection] N(A))] [less than or equal to] 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 graph. If [absolute value of (V(G))] [less than or equal to] 9, then either G [congruent to] [K.sub.6] or G [congruent to] [G.sup.*].

Proof. Recall that G has an even order. It follows that either [absolute value of (V(G))] = 6 or [absolute value of (V(G))] = 8. If [absolute value of (V(G))] = 6, then G [congruent to] [K.sub.6]. So, we may assume [absolute value of (V(G))] = 8. It follows that G has a fragment of cardinality 2. Let A = {x, y} be a fragment of G. Let N(A) = {[x.sub.1], [x.sub.2], [x.sup.3], [x.sup.4], [x.sup.5]}, and let [bar.A] = {z}.

Claim 10. xy [member of] E(G).

Proof. Otherwise, we find that G[N(A)] [congruent to] [C.sub.5]. It follows that G[N(x)] [congruent to] [C.sub.5]. On the other hand, G[N([x.sub.1])] [congruent to] [bar.[K.sub.3]] x [bar.[K.sub.2]]. It follows that G[N(x)] [congruent to] G[N([x.sub.1])], a contradiction.

Let N(x) = {[x.sub.1], [x.sub.2], [x.sub.3], [x.sub.4], y}. By symmetry, we may assume that N(y) = {[x.sub.1], [x.sub.2], [x.sub.3], [x.sub.5], x}. We find that y has at least three neighbors in G[N(x)]. Hence, Lemma 8 implies that G contains [K.sub.4]. It follows that G[N(x)] contains a triangle.

Claim 11. [x.sub.4][x.sub.5] [member of] E(G).

Proof. Suppose [x.sub.4][x.sub.5] [??] E(G). Notice that for i [member of] {4,5}, [absolute value of (N([x.sub.i]) [intersection] (A [union] [bar.A]))] = 2, we see that {[x.sub.4], [x.sub.5]} [??] N([x.sub.1]) [intersection] N([x.sub.2]) [intersection] N([x.sub.3]). Therefore, G[{[x.sub.1], [x.sub.2], [x.sub.3]}] [congruent to] [bar.[K.sub.3]], which implies that G[N(x)] does not contain a triangle, a contradiction.

Now, we observe that G[N(A)] - [x.sub.4][x.sub.5] is 2-regular. Hence, G[N(A)] - [x.sub.4][x.sub.5] is a cycle of length 5. Now, by symmetry, we may assume that {[x.sub.2], [x.sub.3]} [??] N([x.sub.4]) and {[x.sub.1], [x.sub.2]} [??] N([x.sub.5]). It follows that [x.sub.1][x.sub.3] [member of] E(G) since G[N(A)] - [x.sub.4][x.sub.5] is a cycle of length 5. Therefore, we have G [congruent to] [G.sup.*].

Lemma 10. Let G be a TCC-5-connected graph with [absolute value of (V(G))] [greater than or equal to] 10. If G contains [K.sub.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.sub.4]. Let x be a vertex of G, and let N(x) = {[x.sub.1], ..., [x.sub.5]}. Without the loss of generality, let G[{x, [x.sub.1], [x.sub.2], [x.sub.3]}] [congruent to] [K.sub.4].

Claim 12. [absolute value of (N ([x.sub.1]) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]}| [less than or equal to] 1, i [member of] {4,5}.

Proof. We only show that [absolute value of (N([x.sub.4]) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]}| [less than or equal to] 1, and the other one can be handled similarly. Otherwise, by symmetry, we may assume {[x.sub.1], [x.sub.2]} [??] N([x.sub.4]). Let N([x.sub.1]) = {x, [x.sup.2], [x.sup.3], [x.sup.4], [x.sup.1]}. Let A = {x, [x.sup.1]}, and it follows that N(A) = {[x.sup.2], [x.sup.3], [x.sup.4], [x.sup.5], [t.sup.1]}. Furthermore, recall that [absolute value of (V(G))] [greater than or equal to] 10, G - A - N(A) [not equal to] 0. If [t.sub.1] = [x.sub.5], then N(A) is a separator of order 4, a contradiction. Thus, [t.sub.1] [not equal to] [x.sub.5]. Therefore, A is a fragment of G. Furthermore, since [absolute value of (V(G))] [greater than or equal to] 10, we see that [absolute value of (A)] [greater than or equal to] 3. Let B = {x, [x.sub.2]}, and let N([x.sub.2]) = [absolute value of (x, [x.sub.2], [x.sub.3], [x.sub.4], [t.sub.2]}, where [t.sub.2] [member of] N([x.sub.2]) [intersection] [bar.A]. Similarly, B is a fragment of G such that N(B) = {[x.sub.1], [x.sub.3], [x.sub.4], [x.sub.5], [t.sub.2]}. Furthermore, we have [absolute value of ([bar.A])] = [absolute value of ([bar.B])].

Notice that [t.sub.2] [member of] [bar.A] and [t.sub.1] [member of] N(A), we see that [t.sub.1] [not equal to] [t.sub.2]. Now, we see that A [intersection] B = {x}, A [intersection] N(B) = {[x.sub.1]}, B [intersection] N(A) = {[x.sub.2]}, N(A) [intersection] N(B) = {[x.sub.3], [x.sub.4], [x.sub.5]}, [bar.A] [intersection] N(B) = {[t.sub.2]}, and [bar.B] [intersection] N(A) = {[t.sub.1]}.

Now, since [absolute value of ([bar.A])] = [absolute value of ([bar.B])] [greater than or equal to] 3, we find that [absolute value of ([bar.A] [intersection] [bar.B])] [greater than or equal to] 2. Let C = A [union] B. Clearly, C is a fragment with [bar.C] = [bar.A] [intersection] [bar.B]. Notice that N([t.sub.1]) [intersection] C = {[x.sub.1]}, N([t.sub.2]) [intersection] C = {[x.sub.2]}, and N([x.sub.5]) [intersection] C = {x}. Now, Lemma 4 implies that Ad([t.sub.1]; C) [union] Ad([t.sub.2]; C) [union] Ad([x.sub.5]; C) [??] {[x.sub.3], [x.sub.4]}. It follows that either [x.sub.3] or [x.sub.4] has two neighbors in N(C). By symmetry, let [x.sub.3] have two neighbors in N (C). It follows that d ([x.sub.3]) [greater than or equal to] 6, a contradiction. Hence, Claim 12 holds.

Claim 13. N(xi) n {[x.sub.1], [x.sub.2], [x.sub.3]} = 0, i [member of] {4,5}.

Proof. We only show that N([x.sub.4]) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]} = 0, and the other one can be handled similarly. Otherwise, by symmetry, we may assume that [x.sub.4][x.sub.1] [member of] E(G). Now, by Claim 12, N([x.sub.4]) [intersection] {[x.sub.2], [x.sub.3]} = 0. Let A = {x, [x.sub.1]} and N([x.sub.1]) = {x, [x.sub.2], [x.sub.3], [x.sub.4], [t.sub.1]}. Clearly, N(A) = {[x.sub.2], [x.sub.3], [x.sub.4], [x.sub.5], [t.sub.1]} and G - A - N (A) [not equal to] 0. Now, since G is 5-connected, we observe that [t.sub.1] [not equal to] [x.sub.5]. Therefore, A is a fragment of G.

Subclaim 4. N([x.sub.5]) [intersection] {[x.sub.2], [x.sub.3]} = 0. Proof. Suppose [x.sub.2][x.sub.5] [member of] E(G), and then, {x, [x.sub.2]} is fragments of G. Furthermore, we see that G[N(x)] is a connected graph, and this implies that for any t [member of] V(G), G[N(t)] is a connected graph. Let B = {x, [x.sub.2]}, and it follows N(B) = {[x.sub.1], [x.sub.3], [x.sub.4], [x.sub.5], [t.sub.2]}, where [t.sub.2] [member of] N([x.sub.2]) - {x, [x.sub.1], [x.sub.3], [x.sub.5]}. Now, since G is 5-connected, we see that [t.sub.2] [not equal to] [x.sub.4]. We observe that A [intersection] B = {x}, A [intersection] N(B) = {[x.sub.1]}, B [intersection] N(A) = {[x.sub.2]}, N(A) [intersection] N(B) = {[x.sub.3], [x.sub.4], [x.sub.5]}, A [intersection] N(B) = {[t.sub.2]}, and B [intersection] N(A) = {[t.sub.1]}. Furthermore, we see that A [intersection] [bar.B] = 0 and B [intersection] [bar.A] = 0. Notice that G [N (x)] is connected, and we see that for every vertex t of G, G[N(t)] is connected.

Now, since A [intersection] [bar.B] = 0 and [bar.B] [intersection] N(A) = {[t.sub.1]}, the fact [absolute value of ([bar.A])] = [absolute value of ([bar.B])] [greater than or equal to] 3 shows that [absolute value of ([bar.A] [intersection] [bar.B])} [greater than or equal to] 2. Furthermore, [bar.A] [intersection] [bar.B] is a fragment.

If [absolute value of (N([x.sub.3]) [intersection] [bar.A] [intersection] [bar.B])] [greater than or equal to] 2, then G[N([x.sub.3])] has at least two components, a contradiction. Therefore, [absolute value of (N([x.sub.3]) [intersection] ([bar.A] [intersection] [bar.B]))] = 1 and N([x.sub.3]) [intersection] N([bar.A] [intersection] [bar.B]) [not equal to] 0.

On the other hand, by Claim 12, N([x.sub.4]) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]} = {[x.sub.1]}, and N([x.sub.5]) [intersection] {[x.sub.1], [x.sub.2], [x.sub.3]} = {[x.sub.2]}. This fact implies that either [x.sub.3][t.sub.1] [member of] E(G) or [x.sub.3][t.sub.2] [member of] E(G).

By symmetry, we may assume [x.sub.3][t.sub.1] [member of] E(G). Now, since N([x.sub.3]) [intersection] [bar.A] [intersection] [bar.B] [not equal to] 0, we see that G[N([x.sub.3])] has only one vertex of degree 3. On the other hand, we find that G [N (x)] has two vertex of degree 3, and this implies that G[N([x.sub.3])] [congruent to] G[N(x)], a contradiction. This contradiction shows that [x.sub.2][x.sub.5] [??] E(G). By symmetry, [x.sub.3][x.sub.5] [??] E(G). Hence, Subclaim 4 holds.

Subclaim 5. [x.sub.4][x.sub.5] [??] E(G).

Proof. Suppose [x.sub.4][x.sub.5] [??] E (G). Let P' be a graph which is got from the path [x.sub.3][x.sub.2][x.sub.1][x.sub.4][x.sub.5] by adding the edge [x.sub.1][x.sub.3]. Clearly, G[N(x)] [congruent to] P'. Now, since G[N(x)] [congruent to] G[N([x.sub.1])], we find that [x.sub.4][t.sub.1] [member of] E(G). This implies that [absolute value of (N([x.sub.4]) [intersection] [bar.A])] = 1. Let N([x.sub.4]) [intersection] [bar.A] = {[t.sub.4]}. Furthermore, G[N([x.sub.4])] has a triangle, since G[N(x)] has a triangle. Therefore, G[{[t.sub.1], [t.sub.4], [x.sub.5]}] is a triangle. It follows that G[N([x.sub.4])] has a Hamilton cycle. This implies that G[N(x)] [congruent to] G[N([x.sub.4])], a contradiction. Thus, Subclaim 5 holds.

By Subclaims 4 and 5, G[N(x)] has two components, and one of them has exactly one vertex. If [absolute value of (N([x.sub.4]) [intersection] [bar.A])] = 3, then G[N(x)] [congruent to] G[N([x.sub.4])], a contradiction. So, assume that |N ([x.sub.4]) [intersection] [bar.A])] [less than or equal to] 2, which implies that N ([x.sub.4]) [intersection] N (A) [not equal to] 0. By Claim 12 and Subclaim 5, N([x.sub.4]) [intersection] N(A) = {[t.sub.1]}. Now, we see that [K.sub.4] which contains [x.sub.4] is contained in N(A) [union] [bar.A]. Hence, G[N([x.sub.4])] is a connected graph, a contradiction. Thus, Claim 13 holds.

By Claim 13 and Lemma 3, [x.sub.4][x.sub.5] [member of] E(G), and hence, x has type 1. Therefore, G has type 1.

Theorem 7. Let G be a TCC-5-connected graph. If [absolute value of (V(G))] [greater than or equal to] 10, then G has type 1, type 2, type 3, or type 4.

Proof. If G contains [K.sub.4], then Lemma 10 assures us that G has type 1. So, we may assume that G does not contain [K.sub.4]. Hence, Lemma 8 assures us that for any x [member of] V(G), [DELTA] (G [N (x)]) [less than or equal to] 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 graph. If G has type 2, then G is isomorphic to icosahedron.

Proof. Let N(x) = {[x.sub.1], ..., [x.sub.5]}, and let [x.sub.1][x.sub.2] ... [x.sub.5][x.sub.1] be the cycle of G[N(x)]. Furthermore, let N([x.sub.3]) = {[x.sub.2], x, [x.sub.4], [y.sub.1], [y.sub.2]}. Since G has type 2, we may assume that [x.sub.2] * [x.sub.4][y.sub.2][y.sub.1][x.sub.2] is a cycle of G[N([x.sub.3])]. Let N([x.sub.2]) = {[x.sub.1], x, [x.sub.3], [y.sub.1], [y.sub.3]}, and then [y.sub.3] [not equal to] [y.sub.2] and [y.sub.3] [??] {[x.sub.1] ... [x.sub.5]}. Now, [x.sub.1]x[x.sub.3][y.sub.1][y.sub.3][x.sub.1] is a cycle of G[N([x.sub.2])]. Let N([x.sub.4]) = {[x.sub.3], x, [x.sub.5], [y.sub.4], [y.sub.2]}. If [y.sub.4] = [y.sub.3], then, since G has type 2, {[x.sub.1], [x.sub.2], [x.sub.4], [x.sub.5], [y.sub.1], [y.sub.2]} [??] N([y.sub.3]). This implies that d([y.sub.3]) [greater than or equal to] 6, a contradiction. Hence, we have [y.sub.4] [not equal to] [y.sub.3]. Since G does not contain [K.sub.4], we see that [y.sub.4] [??] {[x.sub.1], [x.sub.2], [y.sub.1]}. Now, we observe that [x.sub.3] * [x.sub.5][y.sub.4][y.sub.2][x.sub.3] is the cycle of G[N([x.sub.4])]. Let N([y.sub.2]) = {[x.sub.3], [x.sub.4], [y.sub.4], z, [y.sub.1]}, then, similarly, we can show that z [??] {[x.sub.1], ..., [x.sub.5], [y.sub.1], [y.sub.2], [y.sub.3], [y.sub.4]} and {[y.sub.1], [y.sub.2], [y.sub.3], [y.sub.4]} [??] N(z). Let N(z) = {[y.sub.1], [y.sub.2], [y.sub.3], [y.sub.4], w}, and then w [??] {[x.sub.1], ..., [x.sub.5], [y.sub.1], [y.sub.2], [y.sub.3], [y.sub.4]} and N(w) = {[y.sub.1], [x.sub.1], [x.sub.5], [y.sub.4], z}. It follows that G is icosahedron.

4. Proof of Theorem 5

Since G is 5-regular, we see that [absolute value of (V(G))] 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 [absolute value of (V(G))] [greater than or equal to] 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 TCC-5-connected-graph. Let x [member of] V(G), abc be a path of G[N(x)], and [G.sub.0] = G/{xa, bc}. If G [N (x) - {a, b, c}] [congruent to] [bar.[K.sub.2]], then k ([G.sub.0]) [greater than or equal to] 4.

Proof. Suppose k([G.sub.1]) [less than or equal to] 3. Let [T.sub.1] be a smallest separator of [G.sub.1], and let [A.sub.1] be a [T.sub.1]-fragment. Clearly, [absolute value of ([T.sub.1])] = 3 and {[xa], [bc]} [??] [T.sub.1]. Let T = [T.sub.1] [union] {x,a,b,c} - {[xa], [bc]}. Clearly, [absolute value of (T)] = 5 and {x, a, b, c} [??] T. Furthermore, A = [A.sub.1] is a fragment of G such that N (A) = T. Since G [N (x)] - {a, b, c} is a complete graph, either N (x) [intersection] A = 0 or N (x) [intersection] A = 0, a contradiction. Hence the lemma holds.

Lemma 12. Let G be a TCC-5-connected graph such that [absolute value of (V(G))] [greater than or equal to] 10. If G has type 1, then G can be contracted to a 5-connected H such that 0 < [absolute value of (V(G))] - [absolute value of (V(H))] < 3.

Proof. By the definition of type 1, we know that G contains [K.sub.4] as a subgraph. Since G is vertex transitive graph, every vertex of G is contained in some [K.sub.4]. Let x be a vertex of G, and let N(x) = {[x.sub.1], ..., [x.sub.5]}. Furthermore, without the loss of generality, suppose G[{x, [x.sub.1], [x.sub.2], [x.sub.3]}] [congruent to] [K.sub.4].

Since G has type 1, we may let N([x.sub.1]) = {x, [x.sub.2], [x.sub.3], [y.sub.1], [w.sub.1]}, N([x.sub.2]) = {x , [x.sub.1], [x.sub.3], [y.sub.2], [w.sub.2]}, and N([x.sub.3]) = {x, [x.sub.1], [x.sub.2], [y.sub.3], [w.sub.3]}. Clearly, [x.sub.4], [x.sub.5], [y.sub.1], [w.sub.1], [y.sub.2], [w.sub.2], [y.sub.3], and [w.sub.3] are all different to each other since G has type 1.

Let [G.sub.1] = G/{x[x.sub.1], [x.sub.2][x.sub.3]}, and let [G.sub.2] = G/{x[x.sub.2], [x.sub.1][x.sub.3]}. Now, we see that [delta]([G.sub.1]) [greater than or equal to] 5 and [delta]([G.sub.2]) [greater than or equal to] 5, since [x.sub.4], [x.sub.5], [y.sub.1], [w.sub.1], [y.sub.2], [w.sub.2], [y.sub.3], and [w.sub.3] are all different to each other.

If either k([G.sub.1]) = 5 or k([G.sub.2]) = 5, then we are done. So, by Lemma 11, we may assume that k([G.sub.1]) = 4 and k([G.sub.2]) = 4. Let [T.sub.1] be a smallest separator of [G.sub.1], and let [A.sub.1] be a [T.sub.1]-fragment. Since [delta]([G.sub.1]) [greater than or equal to] 5, we see that [absolute value of ([A.sub.1])] [greater than or equal to] 2 and [absolute value of ([A.sub.1])] [greater than or equal to] 2. Furthermore, we can observe that [T.sub.1] [intersection] {[x[x.sub.1]], [[x.sub.2][x.sub.3]]} [not equal to] 0.

Claim 14. {[x[x.sub.1]], [[x.sub.2][x.sub.3]]} - [T.sub.1] [not equal to] 0.

Proof. Suppose {[x[x.sub.1]], [[x.sub.2][x.sub.3]]} [??] [T.sub.1]. Let T = [T.sub.1] [union] {x, [x.sub.1], [x.sub.2], [x.sub.3]} - [x[x.sub.1]], [[x.sub.2][x.sub.3]]}. It follows that [absolute value of (T)] = 6 and {x, [x.sub.1], [x.sub.2], [x.sub.3]} [??] T. Furthermore, G - T = [A.sub.1] [union] [bar.[A.sub.1]]. Recall that [x.sub.4][x.sub.5] [member of] E(G); then, either N(x) [intersection] [A.sub.1] = 0 or N(x) [intersection] [bar.[A.sub.1]] = 0. Without loss of generality, we may assume that N(x) [intersection] [A.sub.1] = 0. Then, A = [A.sub.1] is a fragment of G such N(A) = T - {x}. It follows that [absolute value of ([bar.A])] > [absolute value of ([bar.[A.sub.1]])] + 1 [greater than or equal to] 3. Since N([x.sub.1]) [intersection] A [not equal to] 0, we see that {[y.sub.1], [w.sub.1]} [??] A [union] N(A). It follows that N([x.sub.1]) [intersection] [bar.A] = {x}. Similarly, N([x.sub.2]) [intersection] [bar.A] = {x}. Hence, N({[x.sub.1], [x.sub.2]}) [intersection] [bar.A] = {x}. Now, Lemma 2 assures us that [absolute value of ([bar.A])] = 1, a contradiction.

By Claim 14, without the loss of generality, let [[x.sub.2][x.sub.3]] [member of] [T.sub.1] and [x[x.sub.1]] [member of] A.

Let T = [T.sub.1] [union] {[x.sub.2], [x.sub.3]} - {[x.sub.2][x.sub.3]]}, and then, [absolute value of (T)] = 5 and {[x.sub.2], [x.sub.3]} [??] T. Furthermore, A = ([A.sub.1] - 1]) [union] {x, [x.sub.1]} is a T-fragment and [bar.A] = [[bar.A].sub.1]. Clearly, [absolute value of (A)] [greater than or equal to] 3 and [absolute value of ([bar.A])] [greater than or equal to] 2.

Similarly, we may assume G has a fragment B such that {x, [x.sub.2]} [??] B and {[x.sub.1], [x.sub.3]} [??] N(B). Furthermore, we may assume that [absolute value of (B)] [greater than or equal to] 3 and [absolute value of ([bar.B])] [greater than or equal to] 2.

Focusing on A and B, we see that x [member of] A + B, [x.sub.2] [member of] N(A) [intersection] B, [x.sub.1] [member of] N(B) [intersection] A, and [x.sub.3] [member of] N(A) [intersection] N(B). If N([x.sub.3]) [intersection] (B [intersection] [bar.A]) [not equal to] 0, then, since [y.sub.3][w.sub.3] [member of] E(G), we see that N([x.sub.3]) [intersection] [bar.B] = 0, a contradiction. Hence, we may assume N([x.sub.3]) [intersection] (B [intersection] [bar.A]) = 0. By symmetry, let N([x.sub.3]) [intersection] (A [intersection] [bar.B]) = 0.

Claim 15. B [intersection] [bar.A] = 0 and [bar.B] [intersection] A = 0.

Proof. Suppose B [intersection] [bar.A] [not equal to] 0. Since N([x.sub.3]) [intersection] (B [intersection] [bar.A]) = 0, Lemma 1 assures us that [bar.B] [intersection] A = 0 and [absolute value of (N(A) [intersection] B)] > [absolute value of (N(B) [intersection] A)]. If B [intersection] A [not equal to] 0, then A [intersection] B is a fragment. On the other hand, we find that N([x.sub.1]) [intersection] A [intersection] B = N([x.sub.3]) [intersection] A [intersection] B = {x}. Now, Lemma 2 assures us that A [intersection] B = {x} and [absolute value of (N(B) [intersection] A)] [greater than or equal to] 2. Thus, [absolute value of (N(A) [intersection] B)] [greater than or equal to] [absolute value of (N(B) [intersection] A)] + 1 [greater than or equal to] 2 + 1 = 3. It follows that [absolute value of (N (A) [intersection] [bar.B])] [less than or equal to] 1. Now, Lemma 1 assures us that [bar.B] [intersection] [bar.A] = 0, a contradiction. Hence, [bar.B] [intersection] [bar.A] = 0. Now, we find that [bar.B] = [bar.B] [intersection] N(A). This implies that [absolute value of ([bar.B] [intersection] N(A))] = [absolute value of ([bar.B])] [greater than or equal to] 2. Since A [intersection] B [not equal to] 0 and B [intersection] A [not equal to] 0, Lemma 1 implies that [absolute value of (N(B) [intersection] A)] [greater than or equal to] 2 and [absolute value of (N(B) [intersection] [bar.A])] [greater than or equal to] 2. Hence, we see that [absolute value of (N(B) [intersection] A)] = [absolute value of (N (B) [intersection] [bar.A])] = 2, which implies that (B [intersection] [bar.A]) is a fragment of G. It follows that N([x.sub.3]) [intersection] (B [intersection] [bar.A]) [not equal to] 0, a contradiction. Hence, we have B [intersection] [bar.A] = 0, and, similarly, [bar.B] [intersection] A = 0.

If [bar.B] [intersection] [bar.A] [not equal to] 0, then Lemma 1 assures us that A [intersection] B is a fragment of G. Since every vertex of G has type 1, we see that N([x.sub.1]) [intersection] A [intersection] B = N([x.sub.3]) [intersection] A [intersection] B = {x}. Now, Lemma 2 assure us that A [intersection] B = {x}. This implies that [absolute value of (N (B) [intersection] A)] [greater than or equal to] 2 and [absolute value of (N(A) [intersection] B)] [greater than or equal to] 2. Now, Lemma 1 assures us that [absolute value of (N (B) [intersection] A)] = [absolute value of (N (A) [intersection] [bar.B])] = [absolute value of (N (A) [intersection] [bar.B])] = [absolute value of (N (B) [intersection] [bar.A])] = 2. Thus, we may assume that N(B) [intersection] A = {[x.sub.1], [x.sub.4]}, N(A) [intersection] B = {[y.sub.1], [w.sub.1]}, N(A) [intersection] B = {[x.sub.2], [x.sub.5]}, and N(B) [intersection] [bar.A] = {[y.sub.1], [w.sub.2]}. Since {[x.sub.1], [x.sub.2], [x.sub.3]} [intersection] N([x.sub.5]) = 0, we see that d([x.sub.5]) = 4, a contradiction. Hence, we may assume that [bar.B] [intersection] [bar.A] = 0. It follows that [bar.B] = [bar.B] [intersection] N(A)_and [bar.A] = [bar.A] [intersection] N(B). Furthermore, [absolute value of ([bar.B] [intersection] N(A))] = [absolute value of ([bar.B]| [greater than or equal to] 2 and [absolute value of ([bar.A] [intersection] N(B))] = [absolute value of ([bar.A]| [greater than or equal to] 2. Now, Lemma 1 assures us that [absolute value of (N (B) [intersection] A)] = [absolute value of (N (A) [intersection] [bar.B])] [absolute value of (N (A) [intersection] B)] = [absolute value of (N (B) [intersection] [bar.A])] = 2. Hence, we see that A [intersection] B is a fragment of G. Now, similarly, we see that d([x.sub.4]) = 4, a contradiction. Hence, we see that either k([G.sub.1]) [greater than or equal to] 5 or k([G.sub.2]) [greater than or equal to] 5.

Lemma 13. Let G be a TCC-5-connected graph such that [absolute value of (V(G))] [greater than or equal to] 10. If G has type 3, then G can be contracted to a 5-connected H such that 0 < [absolute value of (V(G))] - [absolute value of (V (H))] < 3.

Proof. Clearly, G does not contain [K.sub.4]. Suppose G has a fragment of cardinality two, say A = {x, y}. Since G is 5-regular, we see that [absolute value of (N(x) [intersection] N(y))] = 3. Hence, we see that [DELTA](G[N(y)]) [greater than or equal to] 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(x) = {[x.sub.1], ..., [x.sub.5]}. Let [x.sub.1] [x.sub.2][x.sub.3] be a path of G[N(x)]. Furthermore, let N([x.sub.1]) = {x, [x.sub.2], [y.sub.1], [y.sub.2], [y.sub.3]}, N([x.sub.2]) = {x, [x.sub.1], [x.sub.3], [w.sub.1], [w.sub.2]}, and N([x.sub.3]) = {x, [x.sub.2], [z.sub.1], [z.sub.2], [z.sub.3]}. Since G has type 3, we see that {[y.sub.1], [y.sub.2], [y.sub.3]} [intersection] {[x.sub.4], [x.sub.5], [w.sub.1], [w.sub.2]} = 0 and {[z.sub.1], [z.sub.z], [z.sub.3]} [intersection] {[x.sub.4], [x.sub.5], [w.sub.1], [w.sub.2]} = 0.

Let [G.sub.1] = G/{x[x.sub.1], [x.sub.2][x.sub.3]} and [G.sub.2] = G/{x[x.sub.3], [x.sub.1][x.sub.2]}. By Lemma 11, we have k([G.sub.1]) [greater than or equal to] 4 and k([G.sub.2]) [greater than or equal to] 4. If either G1 or [G.sub.2] is 5-connected, then we are done. So we may assume k([G.sub.1]) = 4 and k([G.sub.2]) = 4.

Clearly, [delta]([G.sub.1]) [greater than or equal to] 5 and [delta]([G.sub.2]) [greater than or equal to] 5. For i [member of] {1,2}, let [T.sub.i] be a smallest separator of [G.sub.i] and [A.sub.i] be a [T.sub.i]-fragment. Since [delta]([G.sub.1]) [greater than or equal to] 5 and [delta]([G.sub.2]) [greater than or equal to] 5, we see that every component of G-[T.sub.i] has at least two vertices, where i [member of] {1,2}. Furthermore, [T.sub.1] [intersection] {[x[x.sub.1]], [[x.sub.2][x.sub.3]]} [not equal to] 0 and [T.sub.2] [intersection] {[x[x.sub.3]], [[x.sub.1][x.sub.2]]} [not equal to] 0. Let [mathematical expression not reproducible], where i [member of] {1,2}. It follows that [T.sub.i] [intersection] {[x.sub.1], x, [x.sub.2] , [x.sub.3]} [not equal to] 0, i [member of] {1,2}. Clearly, either [absolute value of ([T'.sub.i] [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]})] = 2 or [absolute value of ([T'.sub.i] [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]})] = 4, i [member of] {1,2}.

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

(1) {x, [x.sub.1], [x.sub.2]} - T [not equal to] 0 and {x, [x.sub.2], [x.sub.3]} - T [not equal to] 0

(2) If either {[x.sub.1], [x.sub.2], [x.sub.3]} [??] T or |[x.sub.1], [x.sub.2], [x.sub.3]} [??] T, then one component of G - T has exactly one vertex

Proof

(1) By symmetry, we only show that {x, [x.sub.1], [x.sub.2]} - T [not equal to] 0, and the other one can be handled similarly. Suppose {[x.sub.1], [x.sub.2], [x.sub.3]} - T [not equal to] 0, which implies that {x, [x.sub.1], [x.sub.2]} [??] T. Let A be a T-fragment. Since G[N(x)] - {[x.sub.1], [x.sub.2], [x.sub.3]} [congruent to] [bar.[K.sub.2]], we see that [x.sub.3] [??] T. Hence, without the loss of generality, let [x.sub.3] [member of] A. Notice the fact that [x.sub.1][x.sub.3] [??] E(G), and we see that A has at least two vertices. Now, the fact that G[N(x)] - {[x.sub.1], [x.sub.2], [x.sub.3]} [congruent to] [bar.[K.sub.2]] assure us that N (x) [intersection] A = {[x.sub.3]}. Similarly, we have N([x.sub.2]) [intersection] A = {[x.sub.3]}. Hence, N({x, [x.sub.2]}) [intersection] A = {[x.sub.3]}. Now Lemma 2 assures us that A = {[x.sub.3]}, a contradiction.

(2) Suppose {[x.sub.1], [x.sub.2], [x.sub.3]} [??] T. Furthermore, suppose every component of G - T has at least two vertices. Let A be a fragment of T. Since G[N(x)] - {[x.sub.1], [x.sub.2], [x.sub.3]} [congruent to] [bar.[K.sub.2]], we see that x [??] T. Without the loss of generality, let x [member of] A. Since both A and [bar.A] have at least two vertices, it follows that A and [bar.A] have at least three vertices.

Notice that N([x.sub.2]) [intersection] A = {x}. If [absolute value of (N([x.sub.1]) [intersection] A)] = 1, then N({[x.sub.2], [x.sub.1]}) [intersection] A = {x}. Now, Lemma 2 assures us that A = {x}, a contradiction. So, we may assume that [absolute value of (N([x.sub.1]) [intersection] A)] [greater than or equal to] 2. Similarly, we see that [absolute value of (N([x.sub.3]) [intersection] A)] [greater than or equal to] 2. Since [absolute value of (N([x.sub.1]) [intersection] A)] [greater than or equal to] 2, we see that [y.sub.2] [member of] N(A). Hence, by symmetry, we may assume [y.sub.1] [member of] A and [y.sub.3] [member of] [bar.A]. It follows that N([x.sub.1]) [intersection] A = {x, [y.sub.1]} and N([x.sub.1]) [intersection] [bar.A] = {[y.sub.3]}. Thus, Lemma 4 assures us that [y.sub.2] [member of] Ad([x.sub.1], [bar.A]). Now, we see that N([y.sub.2]) [intersection] A = {[y.sub.1]}, since G[N([y.sub.2])] -{[y.sub.1], [x.sub.1], [y.sub.3]} [congruent to] [bar.[K.sub.2]]. Notice that N({[x.sub.1], [x.sub.2], [y.sub.1]}) [intersection] A = {x, [y.sub.1]}, and Lemma 2 assures us that A = {x, [y.sub.1]}, a contradiction. Hence, we see that one component of G - T has exactly one vertex. Similarly, we see that the fact {[x.sub.1], x, [x.sub.3]} [??] T assures us that one component of G - T has exactly one vertex.

Claim 17. {[x.sub.1], x, [x.sub.2], [x.sub.3]} - [T'.sub.i] [not equal to] 0, i [member of] {1,2}.

Proof. We only show that {[x.sub.1], x, [x.sub.2], [x.sub.3]} - [T'.sub.i] [not equal to] 0, and the other one can be handled similarly. Suppose {[x.sub.1], x, [x.sub.2], [x.sub.3]} [??] [T'.sub.i]. It follows that [absolute value of ([T'.sub.i])] = 6. Let At be a component of G - [T'.sub.i], [bar.A]' = G - [T'.sub.i] - A'. As [x.sub.4][x.sub.5] [member of] E(G), it follows that either N (x) [intersection] A' = 0 or N(x) [intersection] A' = 0. Similarly,_we see that either N([x.sub.2]) [intersection] A' = 0 or N([x.sub.2]) [intersection] [bar.A]' = 0. Without the loss of generality, let N(x) [intersection] A' = 0. It follows that N([x.sub.2]) [intersection] [bar.A]' = 0, N([x.sub.2]) [intersection] A' [not equal to] 0, and N(x) [intersection] A' [not equal to] 0.

It follows that [T'.sub.i] - {x} is a smallest separator of G. Let T = [T'.sub.i] - {x}, and A = A' is a T--fragment such that [bar.A] = [bar.A]' [union] {x}. If [absolute value of (A)] = 1, then either A = {[w.sub.1]} or A = {[w.sub.2]}. It follows that N([x.sub.1]) [intersection] {[w.sub.1], [w.sub.2]} [intersection] 0, a contradiction. Hence, we have [absolute value of (A)] [greater than or equal to] 3. Notice that [bar.A] = [bar.A]' [union] {x}, and we see that [absolute value of ([bar.A])] [not equal to] 1. It follows that [absolute value of ([bar.A])] [greater than or equal to] 3.

Hence, we see that T is a smallest separator of G such that T [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]} = {[x.sub.1], [x.sub.2], [x.sub.3]}, but both A and [bar.A] have cardinality at least two, which contradicts Claim 16.

By Claim 17, without the loss of generality, we may assume that [T'.sub.1] [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]} = {[x.sub.1], x}. It follows that [absolute value of ([T'.sub.1])] = 5. Let [B.sub.1] be a [T'.sub.1]-fragment. Without the loss of generality, let {[x.sub.2], [x.sub.3]} [??] [B.sub.1]. On the other hand, by Claim 17, either [T'.sub.1] [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]} = {[x.sub.1] , [x.sub.2]} or [T'.sub.2] [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]} = {x, [x.sub.3]}. Furthermore, since every component of G - [T.sub.i] has at least two vertices, we see that every component of G - [T'.sub.i] has at least two vertices, where i [member of] {1, 2}. This implies that every component of G [T'.sub.i] has at least three vertices for each i = 1,2. We will complete the proof of the lemma according the following two cases.

Case 1. [T'.sub.2] [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]} = {[x.sub.3], x}.

It follows that [absolute value of ([T'.sub.2])] = 5. Let [B.sub.2] be a [T'.sub.2]-fragment. Without the loss of generality, suppose {[x.sub.1], [x.sub.2]} [??] [B.sub.2].

Now, we see that [x.sub.2] [member of] [B.sub.1] [intersection] [B.sub.2], [x.sub.1] [member of] [T'.sub.1] [intersection] [B.sub.2], [x.sub.3] [member of] [T'.sub.2] [intersection] [B.sub.1], and x [member of] [T'.sub.1] [intersection] [T'.sub.2].

Claim 18. [[bar.B].sub.1] [intersection] [[bar.B].sub.2] [not equal to] 0.

Proof. Otherwise, assume that [[bar.B].sub.1] [intersection] [[bar.B].sub.2] = 0. Notice that N(x) [intersection] [[bar.B].sub.1] [not equal to] 0 and N(x) [intersection] [[bar.B].sub.2] [not equal to] 0, and we see that N(x) [intersection] [[bar.B].sub.1] [intersection] [T'.sub.2] [not equal to] 0 and N (x) [intersection] [[bar.B].sub.2] [intersection] [T'.sub.1] [not equal to] 0 since G[N(x)] - {[x.sub.1], [x.sub.2], [x.sub.3]} [congruent to] [bar.[K.sub.2]]. Without the loss of generality, let [x.sub.4] [member of] [[bar.B].sub.2] [intersection] [T'.sub.1]. Furthermore, we see that N (x) [intersection] [[bar.B].sub.1] [intersection] [B.sub.2] = 0 and N(x) [intersection] [[bar.B].sub.2] [intersection] [B.sub.1] = 0. If [B.sub.1] [intersection] [[bar.B].sub.2] [not equal to] 0, then Lemma 1 assures us that [[bar.B].sub.1] [intersection] [B.sub.2] = 0. It follows that [absolute value of ([[bar.B].sub.1] [intersection] [T'.sub.2])] [greater than or equal to] [absolute value of ([[bar.B].sub.1])] [greater than or equal to] 3. Now, Lemma 1 assures us that [absolute value of ([[bar.B].sub.2] [intersection] [T'.sub.1])] [greater than or equal to] [absolute value of ([[bar.B].sub.1] [intersection] [T'.sub.2])] [greater than or equal to] 3 and [absolute value of ([[bar.B].sub.2] [intersection] [T'.sub.1])] [greater than or equal to] [absolute value of ([[bar.B].sub.1] [intersection] [T'.sub.2])] [greater than or equal to] 3. This implies that [absolute value of ([T'.sub.2])] [greater than or equal to] 6, a contradiction.

Thus, we may assume that [B.sub.1] [intersection] [[bar.B].sub.2] = 0 and, similarly, [[bar.B].sub.1] [intersection] [B.sub.2] = 0. Similar to the argument of the last paragraph, we have [absolute value of ([[bar.B].sub.1])] [greater than or equal to] 3 and [absolute value of ([[bar.B].sub.2])] [greater than or equal to] 3. It follows that [absolute value of ([[bar.B].sub.2] [intersection] [T'.sub.1])] [greater than or equal to] [absolute value of ([[bar.B].sub.1] [intersection] [T'.sub.2])] [greater than or equal to] 3 and [absolute value of ([[bar.B].sub.2] [intersection] [T'.sub.1])] [greater than or equal to] [absolute value of ([[bar.B].sub.1] [intersection] [T'.sub.2])] [greater than or equal to] [greater than or equal to] 3. Hence, [absolute value of ([T'.sub.1])] [greater than or equal to] 6, a contradiction. Hence, Claim 18 holds.

By Claim 18 and Lemma 1, we see that [B.sub.1] [intersection] [B.sub.2] is a

fragment and N([B.sub.1] [intersection] [B.sub.2]) [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]} = {[x.sub.1], x, [x.sub.3]}. Now, Claim 16 implies that [B.sub.1] [intersection] [B.sub.2] = {[x.sub.2]}. Therefore, {[w.sub.1], [w.sub.2]} [??] [B.sub.1] [union] [T'.sub.1]. If [absolute value of ([B.sub.1] [union] [T'.sub.1])] [less than or equal to] 8, it follows that N([x.sub.3]) [??][B.sub.1] [union] [T'.sub.1] - {[x.sub.4], [x.sub.1], [y.sub.1], [y.sub.2]}, which implies that d([x.sub.3]) [less than or equal to] 4, a contradiction. So, we may assume that [absolute value of ([B.sub.1] [union] [T'.sub.1])] [greater than or equal to] 9. Similarly, we may assume that [absolute value of ([B.sub.2] [union] [T'.sub.2])] [greater than or equal to] 9.

Claim 19. [B.sub.1] [intersection] [[bar.B].sub.2] = 0 and [B.sub.2] [intersection] [[bar.B].sub.1] = 0.

Proof. Clearly, [[bar.B].sub.1] [intersection] [[bar.B].sub.2] is a fragment. It follows that N(x) [intersection] [[bar.B].sub.1] [intersection] [[bar.B].sub.2] [not equal to] 0. Hence, N(x) [intersection] [[bar.B].sub.1] [intersection] [[bar.B].sub.2] = 0 and N(x) [intersection] [[bar.B].sub.2] [intersection] [B.sub.2] = 0, since G[N(x)] - {[x.sub.2], [x.sub.2], [x.sub.3]} [congruent to] [bar.[K.sub.2]].

Now, if [B.sub.1] [intersection] [[bar.B].sub.2] [not equal to] 0, then the fact N([x.sub.2] [intersection] [[bar.B].sub.1] [intersection] [B.sub.2] = 0 assures us that [B.sub.2] [intersection] [[bar.B].sub.1] = 0. Notice that [absolute value of ([B.sub.2] [union] [T'.sub.2])] [greater than or equal to] 9 and [B.sub.1] [intersection] [B.sub.2] = {[x.sub.2]}, and we have [absolute value of ([B.sub.2] [intersection] [T'.sub.1])] [greater than or equal to] 3.

Now, Lemma 1 assures us that [absolute value of ([B.sub.1] [intersection] [T'.sub.2])] [greater than or equal to] [absolute value of ([B.sub.2] [intersection] [T'.sub.1])] [greater than or equal to] 3 and [absolute value of ([B.sub.1] [intersection] [T'.sub.2])] [greater than or equal to] [absolute value of ([B.sub.2] [intersection] [T'.sub.1])] [greater than or equal to] 3. Hence, [absolute value of ([T'.sub.2])] [greater than or equal to] 6, a contradiction. This contradiction implies that [B.sub.1] [intersection] [[bar.B].sub.2] = 0. Similarly, [B.sub.2] [intersection] [[bar.B].sub.1] = 0.

Now, we are ready to complete the proof of Case 1. Notice that [absolute value of ([B.sub.2] [union] [T'.sub.2])] [greater than or equal to] 9, [B.sub.1] [intersection] [B.sub.2] = {[x.sub.2]}, and [B.sub.2] [intersection] [[bar.B].sub.1] = 0, and we see that [absolute value of ([B.sub.2] [intersection] [T'.sub.1])] [greater than or equal to] 3. Similarly, [absolute value of ([B.sub.1] [intersection] [T'.sub.2])] [greater than or equal to] 3. Now, Lemma 1 assures us that [absolute value of ([[bar.B].sub.1] [intersection] [T'.sub.2])] [greater than or equal to] [absolute value of ([B.sub.2] [intersection] [T'.sub.1])] [greater than or equal to] 3. It follows that [absolute value of ([T'.sub.2])] [greater than or equal to] 6, a contradiction.

Case 2. [T'.sub.2] [intersection] {[x.sub.2], x, [x.sub.2], [x.sub.3]} = {[x.sub.2], [x.sub.2]}.

It follows that [absolute value of ([T'.sub.2])] = 5. Let [B.sub.2] be a [T'.sub.2]-fragment. Without the loss of generality, suppose {x, [x.sub.3]} [??] [B.sub.2]. Now, we see that [x.sub.3] [member of] [B.sub.1] [intersection] [B.sub.2], x [member of] [T'.sub.1] [intersection] [B.sub.2], [x.sub.2] [member of] [T'.sub.2] [intersection] [B.sub.1], and [x.sub.2] [member of] [T'.sub.1] [intersection] [T'.sub.2].

Claim 20. [[bar.B].sub.1] [intersection] [[bar.B].sub.2] [not equal to] 0.

Proof. Suppose [[bar.B].sub.1] [intersection] [[bar.B].sub.2] = 0. If [B.sub.1] [intersection] [[bar.B].sub.2] = 0, then [absolute value of ([[bar.B].sub.2] [intersection] [T'.sub.1])] = [absolute value of ([[bar.B].sub.2])] [greater than or equal to] 3. Now, Lemma 1 assures us that [absolute value of ([B.sub.1] [intersection] [T'.sub.2])] [greater than or equal to] [absolute value of ([[bar.B].sub.2] [intersection] [T'.sub.1])] [greater than or equal to] 3. This implies that [absolute value of ([[bar.B].sub.1] [intersection] [T'.sub.2])] [less than or equal to] 2, which implies that [absolute value of ([[bar.B].sub.1] [intersection] [T'.sub.2])] [greater than or equal to] [absolute value of ([[bar.B].sub.2] [intersection] [T'.sub.1])]. Now, Lemma 1 assures us that [[bar.B].sub.1] [intersection] [B.sub.2] = 0, which implies that [absolute value of ([[bar.B].sub.1])] [less than or equal to] 2, a contradiction.

Thus, we may assume that [B.sub.1] [intersection] [[bar.B].sub.2] [not equal to] 0. Similarly, [[bar.B].sub.1] [intersection] [B.sub.2] [not equal to] 0. Thus, both [B.sub.1] [intersection] [[bar.B].sub.2] and [[bar.B].sub.1] [intersection] [B.sub.2] are fragments of G. Without loss of generality, we may assume [y.sub.2] [member of] [B.sub.1] [intersection] [[bar.B].sub.2]. Therefore, [y.sub.3] [member of] [[bar.B].sub.1] [intersection] [B.sub.2] and [y.sub.2] [member of] [T'.sub.1] [intersection] [T'.sub.2] Notice that G[N([y.sub.2])] - {[x.sub.2], [y.sub.2], [y.sub.3]} [congruent to] [bar.[K.sub.2]], and then either [absolute value of (N([y.sub.2]) [intersection] [B.sub.1] [intersection] [[bar.B].sub.2])] = 2 or [absolute value of (N([y.sub.2]) [intersection] [[bar.B].sub.1] [intersection] [B.sub.2])] = 2. Without the loss of generality, let [absolute value of (N([y.sub.2]) [intersection] [B.sub.1] [intersection] [[bar.B].sub.2])] = 2. Now, we find that N({[x.sub.1], [y.sub.2]}) [intersection] [B.sub.1] [intersection] [[bar.B].sub.2] = {[y.sub.1]}. Now, Lemma 2 assures us that [B.sub.1] [intersection] [[bar.B].sub.2] = {[y.sub.1]}. Thus, [y.sub.1][x.sub.2] [member of] E(G). 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.sub.1] [intersection] [B.sub.2] is a fragment, and N([B.sub.1] [intersection] [B.sub.2]) [intersection] {[x.sub.1], x, [x.sub.2], [x.sub.3]} = {x, [x.sub.1], [x.sub.2]}. This contradicts Claim 16.

Lemma 14. Let G be a TCC-5-connected graph such that [absolute value of (V(G))] [greater than or equal to] 10. If G has type 4, then G can be reduced to a 5-connected H such that 0 < [absolute value of (V(G))] - [absolute value of (V (H))] < 3.

Proof. Let x be a vertex of G such that N (x) = {[x.sub.2], ..., [x.sub.5]}. Let [x.sub.2][x.sub.2][x.sub.3][x.sub.4][x.sub.5] be a path of G. Now, Lemma 10 assures us that G does not contain [K.sub.4]. By Lemma 9, every fragment of G has cardinality one or at least four.

Claim 21. Either N([x.sub.2]) [intersection] N([x.sub.3]) = {x} or N([x.sub.3]) [intersection] N([x.sub.4]) = {x}.

Proof. Suppose [absolute value of (N([x.sub.2]) [intersection] N([x.sub.3])| [greater than or equal to] 2 and [absolute value of (N([x.sub.3]) [intersection] N([x.sub.4]))] [greater than or equal to] 2. Let N([x.sub.3]) = {[z.sub.1], [z.sub.2], [x.sub.4], x, [x.sub.2]} and N([x.sub.2]) = {[w.sub.1], [x.sub.1], x, [x.sub.2], [z.sub.1]}, where [z.sub.2][x.sub.4] [member of] E(G). If [w.sub.1][x.sub.1] [??] E(G), then G[N([x.sub.1])] has at least two components, a contradiction. Thus, [w.sub.1][x.sub.1] [member of] E(G). Let N([x.sub.1]) = {[t.sub.1], [t.sub.2], [w.sub.1], [x.sub.2], x}. We may assume [t.sub.1][t.sub.2][w.sub.1][x.sub.2]x is the path of G[N([x.sub.1])]. Now, we see that N([x.sub.2]) [intersection] N([w.sub.1]) = {[x.sub.1]}. Let g [member of] Aut(G) such that g(x) = [x.sub.1]. It follows that g[|.sub.N(x)] is a map from N(x) to N([x.sub.1]). It follows that either g([x.sub.1]) = x or g([x.sub.1]) = [t.sub.1].

If g([x.sub.1]) = x, then g([x.sub.2]) = [x.sub.2], g([x.sub.3]) = [w.sub.1], g([x.sub.4]) = [t.sub.2], and g([x.sub.5]) = [t.sub.1]. Now, since [absolute value of (N([x.sub.2]) [intersection] N([x.sub.3]))] [greater than or equal to] 2, we see that [absolute value of (N([x.sub.2]) [intersection] N([w.sub.1]))] [greater than or equal to] 2, a contradiction. So, we may assume that g([x.sub.1]) = [t.sub.1]. It follows that g([x.sub.2]) = [t.sub.2], g([x.sub.3]) = [w.sub.1], g([x.sub.4]) = [x.sub.2], g([x.sub.5]) = [x.sub.1]. Now, since [absolute value of (N([x.sub.3]) [intersection] N([x.sub.4]))] [greater than or equal to] 2, we see that [absolute value of (N([x.sub.2]) [intersection] N([w.sub.1]))] [greater than or equal to] 2, a contradiction.

Now, by symmetry, assume that N([x.sub.2]) [intersection] N([x.sub.3]) = {x}. Let N([x.sub.2]) = {[y.sub.2], [y.sub.2], [x.sub.1], x, [x.sub.3]} and N([x.sub.3]) = {[z.sub.1], [z.sub.2], [x.sub.4], x, [x.sub.2]}. Furthermore, let [y.sub.1][y.sub.2][x.sub.1]x[x.sub.3] and [z.sub.1][z.sub.2][x.sub.4]x[x.sub.2] be the paths of G[N([x.sub.2])] and G[N([x.sub.3])], respectively. Hence, we may let N([x.sub.1]) = {[w.sub.1], [w.sub.2], [y.sub.2], [x.sub.2], x}, and [w.sub.1][w.sub.2][y.sub.2][x.sub.2]x is the path of G[N([x.sub.1])]. Furthermore, we have [absolute value of (N([x.sub.2]) [intersection] N([x.sub.3])| = 1 and [absolute value of (N([x.sub.3]) [intersection] N([x.sub.4]))] = 2.

Let [G.sub.0] = G/{x[x.sub.1], [x.sub.2][x.sub.3]}. Lemma 11 assures us that k([G.sub.0]) [greater than or equal to] 4. Suppose k([G.sub.0]) = 4. Let T' be a smallest separator of [G.sub.0]. Clearly, we observe that {[x[x.sub.1]], [[x.sub.2][x.sub.3]]} [intersection] T' [not equal to] 0.

Claim 22. {[x[x.sub.1]], [[x.sub.2][x.sub.3]]} [??] T'.

Proof. Suppose [x[x.sub.1]] [??] T'. Let [T.sub.0] = T' [union] {[x.sub.2], [x.sub.3]} - {[[x.sub.2][x.sub.3]]}. Then, [T.sub.0] is a smallest separator of G. Let A be a fragment of [T.sub.0] which contains {x, [x.sub.1]}. It follows that [absolute value of ([bar.A])] [greater than or equal to] 2. Now, Lemma 9 shows that [absolute value of ([bar.A])] = 2. Clearly, [bar.A] [??] {N([x.sub.2]) [intersection] N([x.sub.3])}. Now, since x [member of] A, we see that [absolute value of (N([x.sub.2]) [intersection] N([x.sub.3]))] = 2, which is a contradiction. Hence, we may assume that [x[x.sub.1]] [member of] T'. If [[x.sub.2] [x.sub.3]] [??] T', let [T.sub.0] = T' [union] {x, [x.sub.1]} - {x[x.sub.1]]}. Then, [T.sub.0] is smallest separator G. Let B be a [T.sub.0]-fragment which contains {[x.sub.2], [x.sub.3]}. It follows that [absolute value of (B)] [greater than or equal to] 2. Now, Lemma 9 shows that [absolute value of ([bar.B])] = 2. Clearly, [bar.B] [??] {[x.sub.4], [x.sub.5]}. Hence, [x.sub.1] is adjacent to either [x.sub.4] or [x.sub.5], a contradiction. Hence, [[x.sub.2][x.sub.3]] [member of] T'.

Let [T.sub.0] = T' [union] {x, [x.sub.1], [x.sub.2], [x.sub.3]} - {[x[x.sub.1]], [[x.sub.2][x.sub.3]]}. Let A be a component of G - [T.sub.0], A' = G - [T.sub.0] - A. As [x.sub.4][x.sub.5] [member of] E(G), N (x) [intersection] A = 0 or N(x) [intersection] A' = 0. Similarly, N ([x.sub.2]) [intersection] A = 0 or N([x.sub.2]) [intersection] A' = 0. Without the loss of generality, let N(x) [intersection] A = 0. Then, N([x.sub.2]) [intersection] A' = 0 and N([x.sub.2]) [intersection] A [not equal to] 0, N(x) [intersection] A' [not equal to] 0.

Hence, T = [T.sub.0] - {x} is a smallest separator of G. Let A be a T-fragment. Clearly, [bar.A] = A' [union] {x}. This implies that [absolute value of ([bar.A])] [greater than or equal to] 2. Now, Lemma 9 shows that [absolute value of (A)] = 1. So, A [??] N([x.sub.2]) [intersection] N([x.sub.3]). Recall that x [member of] [bar.A], and we find that [absolute value of (N([x.sub.2]) [intersection] N([x.sub.3]))] [greater than or equal to] 2. This contradicts the fact that N([x.sub.2]) [intersection] N([x.sub.3]) = {x}.

https://doi.org/10.1155/2020/9315494

Data Availability

No data were used to support this study

Conflicts of Interest

The authors declare that they have no conflicts of interest.

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, 1961.

[2] C. Thomassen and B. Toft, "Non-separating induced cycles in graphs," Journal of Combintroial Theory, Series B, vol. 31, pp. 199-224, 1981.

[3] M. Kriesell, "How to contract an essentially 6-connected graph to a 5-connected graph," Discrete Mathematics, vol. 307, pp. 494-510, 2007.

[4] K. Ando and C. Qin, "Some structural properties of minimally contraction-critically 5-connected graphs," Discrete Mathematics, vol. 311, pp. 1084-1097, 2011.

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

[6] C. Qin, X. Yuan, and J. Su, "Some properties of contraction critical 5-connected graphs," Discrete Mathematics, vol. 308, pp. 5742-5756, 2008.

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

[8] M. Kriesell, "A survey on contractible edges in graphs of a given vertex connectivity," Graphs and Combinatorics, vol. 18, pp. 1-30, 2002.

[9] M. Kriesell, "A degree sum condition for the existence of a contractible edge in a K-connected graph," Jouranl of Combintroial Theory, Series B, vol. 82, pp. 81-101, 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 and U. S. R. Murty, Graph Theory with Applications, Macmillan, New York, NY, USA, 1976.

[12] W. Mader, "Generalizations of critical connectivity of graphs," Discrete Mathematics, vol. 72, pp. 267-283, 1988.

Chengfu Qin [ID], (1) Weihua Yang, (2) and Xiaofeng Guo (3)

(1) School of Mathematics Science, Nanning Normal University, Nanning 530001, China

(2) Department of Mathematics, Taiyuan University of Technology, Taiyuan 030024, Shanxi, China

(3) School of Mathematics Science, Xiamen University, XiaMen 310065, China

Correspondence should be addressed to Chengfu Qin; qtclf@163.com

Received 18 April 2020; Accepted 17 June 2020; Published 9 July 2020

Academic Editor: Xiaohua Ding

Caption: Figure 1: The local structure induced by a neighborhood of a vertex: (a) Type 1, (b) type 2, (c) type 3, (d) type 4, and (e) [G.sup.*].
COPYRIGHT 2020 Hindawi Limited
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2020 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Title Annotation:Research Article
Author:Qin, Chengfu; Yang, Weihua; Guo, Xiaofeng
Publication:Discrete Dynamics in Nature and Society
Date:Jul 31, 2020
Words:15148
Previous Article:Complex Network of Scientific Talent Migration in Discrete Dynamics from 2001 to 2013.
Next Article:Passivity Analysis of Markov Jumping Delayed Reaction-Diffusion Neural Networks under Different Boundary Conditions.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters |