# How to Contract a Vertex Transitive 5-Connected Graph

Authors: Chengfu Qin; Weihua Yang; Xiaofeng Guo
Journal: Discrete Dynamics in Nature and Society
 (2020)

---

## Abstract

M.Kriesell conjectured that there existedb, h such that every 5-connected graph G with at least b vertices can be contracted to a 5-connected graph G0 such that 0<VG−VG0<h. We show that this conjecture holds for vertex transitive 5-connected graphs.


---

## Body

## 1. Introduction

All graphs considered here are supposed to be simple, finite, and undirected graphs. For a connected graphG, a subset T⊆VG is called a smallest separator if T=κ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≥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 bk, hk such that every k-connected graph G with at least bk vertices can be contracted to a k-connected graph G0 such that 0<VG−VG0<hk.Clearly, Conjecture1 is true for k≤4. By Kriesell’s examples [3], Conjecture 1 fails for k≥6. Hence, it is still open for k=5.A smallest separatorT 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.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∗.
(a)(b)(c)(d)(e)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<VG−VH<5.In this paper, we will show that Conjecture1 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. LetG be a 5-connected graph which is 5-regular. For any x∈VG, 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:GNx≅K2∪K3(ii)
Type 2:GNx≅C5(iii)
Type 3:GNx≅K2∪P2(iv)
Type 4:GNx≅P4Moreover, fori∈1,2,3,4, G has typei if every vertex of G has type i.Furthermore, we need to introduce the graphG∗ (see Figure 1(e)). One can check that G∗ is vertex transitive, and G∗ can be reduced to K6 by contracting yx1 and xx2.First, we have the following results on the local structure ofTCC-5-connected graphs.Theorem 2.
LetG be a TCC-5-connected graph. If VG≤9, then either G≅K6 or G≅G∗.Theorem 3.
LetG be a TCC-5-connected graph. If VG≥10, then G has type 1, type 2, type 3, or type 4.Theorem 4.
LetG 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.
LetG be a 5-connected vertex transitive graph which is neither K6 nor icosahedron, and then, G can be contracted to a 5-connected G′ such that 0<VG−VG′<3.The organization of the paper is as follows. Section2 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=VG,EG be a graph, where VG denotes the vertex set of G and EG denotes the edge set of G. Let AutG denote the automorphism group of G, and let κG denote the vertex connectivity of G. Let Pn 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∈VG, we define NGx=xxy∈EG. For F⊆VG, we define NGF=∪x∈FNGx−F. Furthermore, let GF 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 ∂F stands for the set of edge with one end in F and the other end in G−F.LetT 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 F¯=VG−F∪T. Clearly, F¯≠∅, and F¯ is also a T-fragment such that NGF=T=NGF¯. A fragment with least cardinality is called an atom. For NGx,dGx, and NGF, we often omit the index G if it is clear from the context.Furthermore, we need some special terminologies for 5-connected graphs. LetA be a fragment of G, and let S=NA. Let x∈S, and y∈Nx∩A. A vertex z is said to be an admissible vertex of x,y;A if both of the following two conditions hold.(1)z∈Nx∩Ny∩S∩V5G,Nz∩A≥2.A vertexz is said to be an admissible vertex of x;A, if z is an admissible vertex of x,y;A for some y∈Nx∩A. Let Adx,y;A(resp. Adx;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 Ve⊆NA.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=NF, T′=NF′. Then, the following statements hold.(1)
IfF∩T′≠∅, then F∩T′≥F′¯∩T,T′∩T≥F¯∩T′(2)
IfF∩T′≠∅ and F∩T′ is not a fragment of G, then F¯∩F′¯=∅ and F∩T′>F′¯∩T,T′∩T>F¯∩T′(3)
IfF∩T′≠∅≠F¯∩F′¯, then both F∩T′ and F¯∩F′¯ are fragments of G, and NF∩T′=T′∩T∪T′∩T∪F∩T′Lemma 2.
(see [4]). Let G be a k-connected graph, and A is a fragment of G. Let B⊆NA. If NB∩A<B, then A=NB∩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∈VG, and A be a fragment such that x∈NA, A≥3, and A¯≥2. If Nx∩A=1, then Adx;A≠∅.Lemma 5.
(see [7]). Let A be a fragment of a contraction-critical 5-connected graph such that A=2, and let t1,t2 be two vertices of NA such that Nt1∩A=Nt2∩A=1. Then, either Adt1;A≠∅ or Adt2;A≠∅.Lemma 6.
LetG be a vertex transitive connected graph, and then, for any two vertices x and y, GNx≅GNy.Proof.
SinceG is a vertex transitive graph, there exist g∈AutG such that xg=y. It follows that Nxg=Ny. Hence, gNx is an isomorphic of GNx and GNy, where gNx is the restriction of g on Nx.Lemma 7.
Letp≥2 be a prime integer, and let G be a vertex transitive graph with κG=p; then, G is a p-regular graph.Proof.
To the contrary, we may assume thatδG>p since δG≥κ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 ofG are disjoint. Otherwise, let A and B be two distinguished atoms of G such that A∩B≠∅. By the definition of atom, A∩B is not a fragment. Lemma 1 assures us that A¯∩B¯=∅ and A∩NB>B¯∩NA. This implies that A>B¯, a contradiction. Thus, any two atoms of G are disjoint.
LetA and C be two atoms of G such that C∩NA≠∅. It follows that A∩C=∅. We show that C⊆NA. Otherwise, suppose C∩A¯≠∅. If C∩A¯ is a fragment of G, then we see that C∩A¯<C, since C∩NA≠∅. This contradicts the definition of atom. So, C∩A¯ is not a fragment of G. Lemma 1 assures us that A∩C¯=∅ and C∩NA>A∩NC=A. It follows that C>A, a contradiction. Hence, C⊆NA. Therefore, NA 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 NA, and hence, A=p. It follows that NA=C. By symmetry, we see that NC=A, which implies that A¯=∅, a contradiction.Lemma 8.
LetG be a TCC-5-connected graph. If G does not contain K4 as subgraph, then for any x∈VG, ΔGNx≤2.Proof.
Clearly, Lemma7 assures us that G is 5-regular, which implies that G has an even order. Suppose that x∈VG with Nx=x1,…,x5 such that x1 adjacent to at least three vertices of Nx. Let A=x, and it follows NA=Nx. If G−A−NA=∅, then G has six vertices. It follows that G≅K6, which implies G contains K4, a contradiction. Hence, we may assume that G−A−NA≠∅. It follows that A is a fragment of G. By symmetry, we assume that x2,x3,x4⊆Nx1. Now, we observe that Nx1∩NA=x2,x3,x4 and Nx1∩A¯=1. Let Nx1∩A¯=t1. Let B=x,x1, and then NB=x2,…,x5,t1. Now, the fact that VG is even assures us that G−B−NB≠∅. It follows that B is a fragment of G. Furthermore, we see that Nt1∩B=x1 and Nx5∩B=x.Now, Lemma 5 assures us that either Adt1;B≠∅ or Adx5;B≠∅. If Adx5;B≠∅, then without loss of generality, assume x2∈Adx5;B. Therefore, GNx is a connected graph. If Adt1;B≠∅, then, similarly, we have that GNx is a connected graph. Now, since G is vertex transitive, the following claims hold.Claim 1.
For anyt∈VG, GNt is a connected graph.Claim 2.
For anyt∈VG, GNt contains a cycle of length 4.Proof.
SinceG is a vertex transitive graph, we only show that Nx1 has a cycle of length 4. By Claim 1, we see that for y∈NB,Ny∩NB≠∅. On the other hand, we observe that Gx2,x3,x4≅K¯3, since G does not contain K4. This implies that every member of x2,x3,x4 is either adjacent to t1 or x5. It follows that Nt1∩x2,x3,x4≥2 or Nx5∩x2,x3,x4≥2. By symmetry, we may assume that Nt1∩x2,x3,x4≥2. It follows that GNx1 contains a cycle of length 4. Hence, for any t∈VG, GNt has a cycle of length 4.
Now, we are ready to complete the proof of Lemma8. By Claim 2, we see that Nxi∩NB≥2 for i∈2,3,4. This implies that t1,x5⊆Nx2∩Nx3∩Nx4. Now, we see that every vertex of NB is adjacent to exactly one vertex of A¯. If B¯=1, say B¯=t, then GNt≅K2,3 and GNx2≅C5, a contradiction. If B¯=2, we can observe that B¯ has a vertex with a degree of at most 4, a contradiction. Hence, we may assume that B¯=3. Now, Lemma 4 shows that Adx2;B¯≠∅, which implies Nz∩A¯≥2 for some z∈NB, a contradiction.Lemma 9.
LetG be a TCC-5-connected graph. If G has type 4, then G is essentially 6-connected.Proof.
SinceG has type 4, we see that for any x∈VG, ΔGNx≤2.Claim 3.
IfA is a fragment of G, then A≠2.Proof.
SupposeA=x,y. If xy∈EG, then x has three neighbors in GNy, a contradiction. So, we may assume xy∉EG. It follows that GNA≅P5. Let x1x2x3x4x5 be the path of GNA. It follows that Nx2∩A¯=Nx3∩A¯=Nx4∩A¯=1. If A¯≥3, then Lemma 4 implies that Adx3,A¯≠∅. Hence, either x2∈Adx3,A¯ or x4∈Adx3,A¯. This is a contradiction, since Nx2∩A¯=Nx4∩A¯=1. Hence, we may assume that A¯≤2. If A¯=1, then we see that dx1<5, a contradiction. So, we may assume A¯=2. It follows that VG=9, which contradicts the fact that G has an even order. Hence, Claim 3 holds.Claim 4.
IfA is a fragment of G, then A¯≠3.Proof.
We first show thatGA is a connected graph. Otherwise, let A1 be a component of GA such that A1 has exactly one vertex. It follows that A2=A−A1 is a fragment of cardinality 2, a contradiction. Next, we show that GA is a path. Suppose GA is a cycle, then a simple calculation shows that ∂A=9. This implies that one vertex of NA, say w, has exactly one neighbor in A. Now, we find that A−Nw is a fragment of cardinality 2, a contradiction.
Letxyz be the path of GA, and let NA=x1,…,x5. Without the loss of generality, let Ny=x,x1,x2,x3,z.Subclaim 1.Nx∩x1,x2,x3=2 and Nz∩x1,x2,x3=2.Proof. Notice thatG has type 4; we find that Nx∩x1,x2,x3≤2. If Nx∩x1,x2,x3≤1, then we find that dx≤4, a contradiction. Hence, Nx∩x1,x2,x3=2. By symmetry, Nz∩x1,x2,x3=2.Without the loss of generality, we may assume thatx1,x2⊆Nx. Now, if x1,x2⊆Nz, then xx1zx2x is a cycle of GNy, a contradiction. Therefore, x2,x3⊆Nz, which implies that x4,x5⊆Nx∩Nz.Subclaim 2.Gx1,x2,x3≅K3¯.Proof. Ifx1x2∈EG, then Ny has a triangle, a contradiction. It follows that x1x2∉EG. Similarly, we have x2x3∉EG. Furthermore, if x1x3∉EG, then we find that there is a cycle of length four in Ny, a contradiction. Thus, x1x3∉EG. It follows that Gx1,x2,x3≅K3¯.
Now, we are ready to complete the proof of Claim4. Focusing on x2, we find that Nx2∩NA≠∅ since GNx2 is connected. By Subclaim 2, we may assume that x4∈Nx2. Now, we find that there is a cycle of length four in Nx2, a contradiction.Claim 5.
For every smallest separatorT, G−T has exactly two components.Proof.
Otherwise, assume thatG−T has at least three components. Let A1, A2, and A3 be three connected components of G−T.Subclaim 3. For anyy∈T, Ny∩T=2, and Ny∩Ai=1,i∈1,2,3.Proof. Lety∈T, let Ny=y1,…,y5. Without the loss of generality, we may assume that yi∈Ai,i∈1,2,3. Now, we find that Ny∩T≠∅, since G has type 4. Suppose y4∈Ny∩T. If Ny∩T=y4, then the fact that GNy is connected shows that y4 has three neighbors in GNy, which contradicts the fact that G has type 4. So, we have Ny∩T=y4,y5. It follows that Ny∩Ai=1,i∈1,2,3 and Ny∩T=2.By Subclaim 3, δGT=2, which implies that GT is a cycle of length 5. Hence, we see that Ai≠1,i∈1,2,3. Furthermore, by Subclaims 3 and 4, Ai≠3 for each i=1,2,3. Focusing on A1, we find that A¯1=A2∪A3, which implies that A¯1≥6. Recall that Nx∩A1=1, and Lemma 4 shows that Adx;A1≠∅. Without the loss of generality, assume that y∈Adx;A1. This implies that Ny∩A1≥2, which contradicts Subclaim 3. Hence, Claim 5 holds.
Next, we assume thatG is not essentially 6-connected. It follows that there is a fragment B such that B≥2 and B¯≥2. Let ℬ=BB is a fragment such that B≥2 and B¯≥2, and let t=minBB∈ℬ. By Claims 3 and 4, we see that t≥4. Let ℬ1=BB∈ℬ and B=t. Let A∈ℬ1, and let y∈NA. Now, since G is vertex transitive, every vertex of G is contained in some member of ℬ1. Therefore, there exist B∈ℬ1 such that y∈B. Next, we will analyse the local structure of A and B.Claim 6.
IfA∩B≠∅, then A¯∩B¯≠∅.Proof.
SupposeA∩B≠∅ and A¯∩B¯=∅. Now, Lemma 1 assures us that A∩NB≥B¯∩NA. It follows that(2)A=A∩B+A∩NB+A∩B¯≥A∩B+B¯∩NA+A∩B¯>B¯∩NA+A∩B¯=B¯.
This contradicts the choice ofA.Claim 7.
A∩B¯≠∅ if and only if A¯∩B≠∅.Proof.
SupposeA∩B¯≠∅. Now, Lemma 1 assures us that A∩NB≥B∩NA. If A¯∩B=∅, then we see that(3)A=A∩B+A∩NB+A∩B¯≥A∩B+B∩NA+A∩B¯>A∩B+B∩NA=B.
This contradicts the choice ofA. Hence, we see that A¯∩B≠∅. By symmetry, we see that A¯∩B≠∅ implies A∩B¯≠∅.Claim 8.
A∩B=∅.Proof.
SupposeA∩B≠∅. By Claim 6, we know that A¯∩B¯≠∅. Hence, A∩B is a fragment of G. By the choice of A, we know that A∩B=1. Furthermore, since A¯∩B¯≠∅, Lemma 1 assures us that B¯∩NA≥A∩NB.
IfA∩B¯=∅, then Claim 7 assures us that A¯∩B=∅. Furthermore, A=B≥4 implies that A∩NB=B∩NA≥3. Hence, we find that NA≥B∩NA+B¯∩NA≥B∩NA+A∩NB≥6, a contradiction.
So, we may assumeA∩B¯≠∅. Then, Claim 7 assures us that A¯∩B≠∅. Hence, both A∩B¯ and B∩A¯ are fragments of G. By the choice of A and B, we know that A∩B¯=B∩A¯=1. It follows that A∩NB=B∩NA.
SinceA¯∩B¯≠∅, Lemma 1 assure us that B¯∩NA≥A∩NB. If A∩NB≥3, then NA≥B∩NA+B¯∩NA≥6, a contradiction.
Therefore, letA∩NB=2. It follows that A∩NB=B∩NA=2. Since A¯∩B¯≠∅ and A∩B≠∅, Lemma 1 assures us that A¯∩NB=B¯∩NA=2. This implies that NB∩NA=1. Let NB∩NA=t. Now, Nt∩A∩B≠∅, since A∩B is a fragment. Similarly, we find that Nt∩A∩B¯≠∅, Nt∩A¯∩B¯≠∅, and Nt∩A¯∩B≠∅. Now, we find that GNt has at least two components, a contradiction.Claim 9.
A∩B¯=∅ and B∩A¯=∅.Proof.
SupposeA∩B¯≠∅. By Claim 7, we see that A¯∩B≠∅. Hence, both A∩B¯ and A¯∩B are fragments of G. By the choice of A, we see that A∩B¯=A¯∩B=1. It follows that A∩NB=B∩NA≥3.
IfA¯∩B¯≠∅, then B¯∩NA≥A∩NB. Hence, we see that NA≥B∩NA+B¯∩NA≥6, a contradiction.
Hence, we may assume thatA¯∩B¯=∅. Then, by the choice of B, we know that B¯≥B. It follows that B¯∩NA≥3. Hence, we find that NA≥B∩NA+B¯∩NA≥6, a contradiction.
Now, we are ready to complete the proof of the Lemma. By Claims8 and 9, we find that A=A∩NB and B=B∩NA. Now, we find that B¯∩NA≤NA−B∩NA≤1, since B∩NA=B≥4. It follows that B¯∩NA<A∩NB. Now, Lemma 1 implies that A¯∩B¯=∅. It follows that B¯=B¯∩NA≤1, a contradiction.


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

In this section, since Lemma7 holds, all TCC-5-connected graphs were supposed to be 5-regular and have an even order.Theorem 6.
LetG be a TCC-5-connected graph. If VG≤9, then either G≅K6 or G≅G∗.Proof.
Recall thatG has an even order. It follows that either VG=6 or VG=8. If VG=6, then G≅K6. So, we may assume VG=8. It follows that G has a fragment of cardinality 2. Let A=x,y be a fragment of G. Let NA=x1,x2,x3,x4,x5, and let A¯=z.Claim 10.
xy∈EG.Proof.
Otherwise, we find thatGNA≅C5. It follows that GNx≅C5. On the other hand, GNx1≅K3¯×K2¯. It follows that GNx≅GNx1, a contradiction.
LetNx=x1,x2,x3,x4,y. By symmetry, we may assume that Ny=x1,x2,x3,x5,x. We find that y has at least three neighbors in GNx. Hence, Lemma 8 implies that G contains K4. It follows that GNx contains a triangle.Claim 11.
x4x5∈EG.Proof.
Supposex4x5∉EG. Notice that for i∈4,5, Nxi∩A∪A¯=2, we see that x4,x5⊆Nx1∩Nx2∩Nx3. Therefore, Gx1,x2,x3≅K3¯, which implies that GNx does not contain a triangle, a contradiction.
Now, we observe thatGNA−x4x5 is 2-regular. Hence, GNA−x4x5 is a cycle of length 5. Now, by symmetry, we may assume that x2,x3⊆Nx4 and x1,x2⊆Nx5. It follows that x1x3∈EG since GNA−x4x5 is a cycle of length 5. Therefore, we have G≅G∗.Lemma 10.
LetG be a TCC-5-connected graph with VG≥10. If G contains K4 as a subgraph, then G has type 1.Proof.
SinceG is a vertex transitive graph, we know that every vertex of G is contained in a K4. Let x be a vertex of G, and let Nx=x1,…,x5. Without the loss of generality, let Gx,x1,x2,x3≅K4.Claim 12.
Nxi∩x1,x2,x3≤1,i∈4,5.Proof.
We only show thatNx4∩x1,x2,x3≤1, and the other one can be handled similarly. Otherwise, by symmetry, we may assume x1,x2⊆Nx4. Let Nx1=x,x2,x3,x4,x1. Let A=x,x1, and it follows that NA=x2,x3,x4,x5,t1. Furthermore, recall that VG≥10, G−A−NA≠∅. If t1=x5, then NA is a separator of order 4, a contradiction. Thus, t1≠x5. Therefore, A is a fragment of G. Furthermore, since VG≥10, we see that A¯≥3. Let B=x,x2, and let Nx2=x,x2,x3,x4,t2, where t2∈Nx2∩A¯. Similarly, B is a fragment of G such that NB=x1,x3,x4,x5,t2. Furthermore, we have A¯=B¯.
Notice thatt2∈A¯ and t1∈NA, we see that t1≠t2. Now, we see that A∩B=x, A∩NB=x1, B∩NA=x2, NA∩NB=x3,x4,x5, A¯∩NB=t2, and B¯∩NA=t1.
Now, sinceA¯=B¯≥3, we find that A¯∩B¯≥2. Let C=A∪B. Clearly, C is a fragment with C¯=A¯∩B¯. Notice that Nt1∩C=x1, Nt2∩C=x2, and Nx5∩C=x. Now, Lemma 4 implies that Adt1;C∪Adt2;C∪Adx5;C⊆x3,x4. It follows that either x3 or x4 has two neighbors in NC. By symmetry, let x3 have two neighbors in NC. It follows that dx3≥6, a contradiction. Hence, Claim 12 holds.Claim 13.
Nxi∩x1,x2,x3=∅,i∈4,5.Proof.
We only show thatNx4∩x1,x2,x3=∅, and the other one can be handled similarly. Otherwise, by symmetry, we may assume that x4x1∈EG. Now, by Claim 12, Nx4∩x2,x3=∅. Let A=x,x1 and Nx1=x,x2,x3,x4,t1. Clearly, NA=x2,x3,x4,x5,t1 and G−A−NA≠∅. Now, since G is 5-connected, we observe that t1≠x5. Therefore, A is a fragment of G.Subclaim 4.Nx5∩x2,x3=∅.Proof. Supposex2x5∈EG, and then, x,x2 is fragments of G. Furthermore, we see that GNx is a connected graph, and this implies that for any t∈VG, GNt is a connected graph. Let B=x,x2, and it follows NB=x1,x3,x4,x5,t2, where t2∈Nx2−x,x1,x3,x5. Now, since G is 5-connected, we see that t2≠x4. We observe that A∩B=x, A∩NB=x1, B∩NA=x2, NA∩NB=x3,x4,x5, A¯∩NB=t2, and B¯∩NA=t1. Furthermore, we see that A∩B¯=∅ and B∩A¯=∅. Notice that GNx is connected, and we see that for every vertex t of G, GNt is connected.
Now, sinceA∩B¯=∅ and B¯∩NA=t1, the fact A¯=B¯≥3 shows that A¯∩B¯≥2. Furthermore, A¯∩B¯ is a fragment.
IfNx3∩A¯∩B¯≥2, then GNx3 has at least two components, a contradiction. Therefore, Nx3∩A¯∩B¯=1 and Nx3∩NA¯∩B¯≠∅.
On the other hand, by Claim12, Nx4∩x1,x2,x3=x1, and Nx5∩x1,x2,x3=x2. This fact implies that either x3t1∈EG or x3t2∈EG.
By symmetry, we may assumex3t1∈EG. Now, since Nx3∩A¯∩B¯≠∅, we see that GNx3 has only one vertex of degree 3. On the other hand, we find that GNx has two vertex of degree 3, and this implies that GNx3≅GNx, a contradiction. This contradiction shows that x2x5∉EG. By symmetry, x3x5∉EG. Hence, Subclaim 4 holds.Subclaim 5.x4x5∉EG.Proof. Supposex4x5∉EG. Let P′ be a graph which is got from the path x3x2x1x4x5 by adding the edge x1x3. Clearly, GNx≅P′. Now, since GNx≅GNx1, we find that x4t1∈EG. This implies that Nx4∩A¯=1. Let Nx4∩A¯=t4. Furthermore, GNx4 has a triangle, since GNx has a triangle. Therefore, Gt1,t4,x5 is a triangle. It follows that GNx4 has a Hamilton cycle. This implies that GNx≅GNx4, a contradiction. Thus, Subclaim 5 holds.
By Subclaims 4 and 5,GNx has two components, and one of them has exactly one vertex. If Nx4∩A¯=3, then GNx≅GNx4, a contradiction. So, assume that Nx4∩A¯≤2, which implies that Nx4∩NA≠∅. By Claim 12 and Subclaim 5, Nx4∩NA=t1. Now, we see that K4 which contains x4 is contained in NA∪A¯. Hence, GNx4 is a connected graph, a contradiction. Thus, Claim 13 holds.
By Claim13 and Lemma 3, x4x5∈EG, and hence, x has type 1. Therefore, G has type 1.Theorem 7.
LetG be a TCC-5-connected graph. If VG≥10, then G has type 1, type 2, type 3, or type 4.Proof.
IfG contains K4, then Lemma 10 assures us that G has type 1. So, we may assume that G does not contain K4. Hence, Lemma 8 assures us that for any x∈VG, ΔGNx≤2. Now, Lemma 3 assures us that G has either type 2 or type 3 or type 4.Theorem 8.
LetG be a TCC-5-connected graph. If G has type 2, then G is isomorphic to icosahedron.Proof.
LetNx=x1,…,x5, and let x1x2⋯x5x1 be the cycle of GNx. Furthermore, let Nx3=x2,x,x4,y1,y2. Since G has type 2, we may assume that x2xx4y2y1x2 is a cycle of GNx3. Let Nx2=x1,x,x3,y1,y3, and then y3≠y2 and y3∉x1,…,x5. Now, x1xx3y1y3x1 is a cycle of GNx2. Let Nx4=x3,x,x5,y4,y2. If y4=y3, then, since G has type 2, x1,x2,x4,x5,y1,y2⊆Ny3. This implies that dy3≥6, a contradiction. Hence, we have y4≠y3. Since G does not contain K4, we see that y4∉x1,x2,y1. Now, we observe that x3xx5y4y2x3 is the cycle of GNx4. Let Ny2=x3,x4,y4,z,y1, then, similarly, we can show that z∉x1,…,x5,y1,y2,y3,y4 and y1,y2,y3,y4⊆Nz. Let Nz=y1,y2,y3,y4,w, and then w∉x1,…,x5,y1,y2,y3,y4 and Nw=y1,x1,x5,y4,z. It follows that G is icosahedron.


## 4. Proof of Theorem5

SinceG is 5-regular, we see that VG 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 VG≥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.
LetG be a TCC-5-connected-graph. Let x∈VG, abc be a path of GNx, and G0=G/xa,bc. If GNx−a,b,c≅K2, then κG0≥4.Proof.
SupposeκG1≤3. Let T1 be a smallest separator of G1, and let A1 be a T1-fragment. Clearly, T1=3 and xa,bc⊆T1. Let T=T1∪x,a,b,c−xa,bc. Clearly, T=5 and x,a,b,c⊆T. Furthermore, A=A1 is a fragment of G such that NA=T. Since GNx−a,b,c is a complete graph, either Nx∩A=∅ or Nx∩A¯=∅, a contradiction. Hence the lemma holds.Lemma 12.
LetG be a TCC-5-connected graph such that VG≥10. If G has type 1, then G can be contracted to a 5-connected H such that 0<VG−VH<3.Proof.
By the definition of type 1, we know thatG contains K4 as a subgraph. Since G is vertex transitive graph, every vertex of G is contained in some K4. Let x be a vertex of G, and let Nx=x1,…,x5. Furthermore, without the loss of generality, suppose Gx,x1,x2,x3≅K4.
SinceG has type 1, we may let Nx1=x,x2,x3,y1,w1, Nx2=x,x1,x3,y2,w2, and Nx3=x,x1,x2,y3,w3. Clearly, x4,x5,y1,w1,y2, w2,y3, and w3 are all different to each other since G has type 1.
LetG1=G/xx1,x2x3, and let G2=G/xx2,x1x3. Now, we see that δG1≥5 and δG2≥5, since x4,x5,y1,w1,y2,w2,y3, and w3 are all different to each other.
If eitherκG1=5 or κG2=5, then we are done. So, by Lemma 11, we may assume that κG1=4 and κG2=4. Let T1 be a smallest separator of G1, and let A1 be a T1-fragment. Since δG1≥5, we see that A1≥2 and A1¯≥2. Furthermore, we can observe that T1∩xx1,x2x3≠∅.Claim 14.
xx1,x2x3−T1≠∅.Proof.
Supposexx1,x2x3⊆T1. Let T=T1∪x,x1,x2,x3−xx1,x2x3. It follows that T=6 and x,x1,x2,x3⊆T. Furthermore, G−T=A1∪A1¯. Recall that x4x5∈EG; then, either Nx∩A1=∅ or Nx∩A1¯=∅. Without loss of generality, we may assume that Nx∩A1=∅. Then, A=A1 is a fragment of G such NA=T−x. It follows that A¯≥A1¯+1≥3. Since Nx1∩A≠∅, we see that y1,w1⊆A∪NA. It follows that Nx1∩A¯=x. Similarly, Nx2∩A¯=x. Hence, Nx1,x2∩A¯=x. Now, Lemma 2 assures us that A¯=1, a contradiction.
By Claim14, without the loss of generality, let x2x3∈T1 and xx1∈A.
LetT=T1∪x2,x3−x2x3, and then, T=5 and x2,x3⊆T. Furthermore, A=A1−xx1∪x,x1 is a T-fragment and A¯=A¯1. Clearly, A≥3 and A¯≥2.
Similarly, we may assumeG has a fragment B such that x,x2⊆B and x1,x3⊆NB. Furthermore, we may assume that B≥3 and B¯≥2.
Focusing onA and B, we see that x∈A∩B, x2∈NA∩B, x1∈NB∩A, and x3∈NA∩NB. If Nx3∩B∩A¯≠∅, then, since y3w3∈EG, we see that Nx3∩B¯=∅, a contradiction. Hence, we may assume Nx3∩B∩A¯=∅. By symmetry, let Nx3∩A∩B¯=∅.Claim 15.
B∩A¯=∅ and B¯∩A=∅.Proof.
SupposeB∩A¯≠∅. Since Nx3∩B∩A¯=∅, Lemma 1 assures us that B¯∩A=∅ and NA∩B>NB∩A. If B¯∩A¯≠∅, then A∩B is a fragment. On the other hand, we find that Nx1∩A∩B=Nx3∩A∩B=x. Now, Lemma 2 assures us that A∩B=x and NB∩A≥2. Thus, NA∩B≥NB∩A+1≥2+1=3. It follows that NA∩B¯≤1. Now, Lemma 1 assures us that B¯∩A¯=∅, a contradiction. Hence, B¯∩A¯=∅. Now, we find that B¯=B¯∩NA. This implies that B¯∩NA=B¯≥2. Since A∩B≠∅ and B∩A¯≠∅, Lemma 1 implies that NB∩A≥2 and NB∩A¯≥2. Hence, we see that NB∩A=NB∩A¯=2, which implies that B∩A¯ is a fragment of G. It follows that Nx3∩B∩A¯≠∅, a contradiction. Hence, we have B∩A¯=∅, and, similarly, B¯∩A=∅.
IfB¯∩A¯≠∅, then Lemma 1 assures us that A∩B is a fragment of G. Since every vertex of G has type 1, we see that Nx1∩A∩B=Nx3∩A∩B=x. Now, Lemma 2 assure us that A∩B=x. This implies that NB∩A≥2 and NA∩B≥2. Now, Lemma 1 assures us that NB∩A=NA∩B¯=NA∩B=NB∩A¯=2. Thus, we may assume that NB∩A=x1,x4,NA∩B¯=y1,w1,NA∩B=x2,x5,andNB∩A¯=y1,w2. Since x1,x2,x3∩Nx5=∅, we see that dx5=4, a contradiction. Hence, we may assume that B¯∩A¯=∅. It follows that B¯=B¯∩NA and A¯=A¯∩NB. Furthermore, B¯∩NA=B¯≥2 and A¯∩NB=A¯≥2. Now, Lemma 1 assures us that NB∩A=NA∩B¯=NA∩B=NB∩A¯=2. Hence, we see that A∩B is a fragment of G. Now, similarly, we see that dx4=4, a contradiction. Hence, we see that either κG1≥5 or κG2≥5.Lemma 13.
LetG be a TCC-5-connected graph such that VG≥10. If G has type 3, then G can be contracted to a 5-connected H such that 0<VG−VH<3.Proof.
Clearly,G does not contain K4. Suppose G has a fragment of cardinality two, say A=x,y. Since G is 5-regular, we see that Nx∩Ny=3. Hence, we see that ΔGNy≥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 Nx=x1,…,x5. Let x1x2x3 be a path of GNx. Furthermore, let Nx1=x,x2,y1,y2,y3, Nx2=x,x1,x3,w1,w2, and Nx3=x,x2,z1,z2,z3. Since G has type 3, we see that y1,y2,y3∩x4,x5,w1,w2=∅ and z1,zz,z3∩x4,x5,w1,w2=∅.
LetG1=G/xx1,x2x3 and G2=G/xx3,x1x2. By Lemma 11, we have κG1≥4 and κG2≥4. If either G1 or G2 is 5-connected, then we are done. So we may assume κG1=4 and κG2=4.
Clearly,δG1≥5 and δG2≥5. For i∈1,2, let Ti be a smallest separator of Gi and Ai be a Ti-fragment. Since δG1≥5 and δG2≥5, we see that every component of G−Ti has at least two vertices, where i∈1,2. Furthermore, T1∩xx1,x2x3≠∅ and T2∩xx3,x1x2≠∅. Let Ti′=Ti∪∪ab∈Tia,b−∪ab∈Tia,b, where i∈1,2. It follows that Ti′∩x1,x,x2,x3≠∅, i∈1,2. Clearly, either Ti′∩x1,x,x2,x3=2 or Ti′∩x1,x,x2,x3=4, i∈1,2.Claim 16.
For a smallest separatorT of G, the following holds.(1)
x,x1,x2−T≠∅ and x,x2,x3−T≠∅(2)
If eitherx1,x2,x3⊆T or x1,x,x3⊆T, then one component of G−T has exactly one vertexProof.
(1)
By symmetry, we only show thatx,x1,x2−T≠∅, and the other one can be handled similarly. Suppose x,x1,x2−T≠∅, which implies that x,x1,x2⊆T. Let A be a T-fragment. Since GNx−x1,x2,x3≅K2, we see that x3∉T. Hence, without the loss of generality, let x3∈A. Notice the fact that x1x3∉EG, and we see that A has at least two vertices. Now, the fact that GNx−x1,x2,x3≅K2 assure us that Nx∩A=x3. Similarly, we have Nx2∩A=x3. Hence, Nx,x2∩A=x3. Now Lemma 2 assures us that A=x3, a contradiction.(2)
Supposex1,x2,x3⊆T. Furthermore, suppose every component of G−T has at least two vertices. Let A be a fragment of T. Since GNx−x1,x2,x3≅K2, we see that x∉T . Without the loss of generality, let x∈A. Since both A and A¯ have at least two vertices, it follows that A and A¯ have at least three vertices.
Notice thatNx2∩A=x. If Nx1∩A=1, then Nx2,x1∩A=x. Now, Lemma 2 assures us that A=x, a contradiction. So, we may assume that Nx1∩A≥2. Similarly, we see that Nx3∩A≥2. Since Nx1∩A≥2, we see that y2∈NA. Hence, by symmetry, we may assume y1∈A and y3∈A¯. It follows that Nx1∩A=x,y1 and Nx1∩A¯=y3. Thus, Lemma 4 assures us that y2∈Adx1,A¯. Now, we see that Ny2∩A=y1, since GNy2−y1,x1,y3≅K2. Notice that Nx1,x2,y2∩A=x,y1, and Lemma 2 assures us that A=x,y1, a contradiction. Hence, we see that one component of G−T has exactly one vertex. Similarly, we see that the fact x1,x,x3⊆T assures us that one component of G−T has exactly one vertex.Claim 17.
x1,x,x2,x3−Ti′≠∅, i∈1,2.Proof.
We only show thatx1,x,x2,x3−T1′≠∅, and the other one can be handled similarly. Suppose x1,x,x2,x3⊆T1′. It follows that T1′=6. Let A′ be a component of G−T1′, A′¯=G−T1′−A′. As x4x5∈EG, it follows that either Nx∩A′=∅ or Nx∩A′¯=∅. Similarly, we see that either Nx2∩A′=∅ or Nx2∩A′¯=∅. Without the loss of generality, let Nx∩A′=∅. It follows that Nx2∩A′¯=∅, Nx2∩A′≠∅, and Nx∩A′¯≠∅.
It follows thatT1′−x is a smallest separator of G. Let T=T1′−x, and A=A′ is a T− fragment such that A¯=A′¯∪x. If A=1, then either A=w1 or A=w2. It follows that Nx1∩w1,w2≠∅, a contradiction. Hence, we have A≥3. Notice that A¯=A′¯∪x, and we see that A¯≠1. It follows that A¯≥3.
Hence, we see thatT is a smallest separator of G such that T∩x1,x,x2,x3=x1,x2,x3, but both A and A¯ have cardinality at least two, which contradicts Claim 16.
By Claim17, without the loss of generality, we may assume that T1′∩x1,x,x2,x3=x1,x. It follows that T1′=5. Let B1 be a T1′-fragment. Without the loss of generality, let x2,x3⊆B1. On the other hand, by Claim 17, either T2′∩x1,x,x2,x3=x1,x2 or T2′∩x1,x,x2,x3=x,x3. Furthermore, since every component of G−Ti has at least two vertices, we see that every component of G−Ti′ has at least two vertices, where i∈1,2. This implies that every component of G−Ti′ 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.
T2′∩x1,x,x2,x3=x3,x.
It follows thatT2′=5. Let B2 be a T2′-fragment. Without the loss of generality, suppose x1,x2⊆B2.
Now, we see thatx2∈B1∩B2, x1∈T1′∩B2, x3∈T2′∩B1, and x∈T1′∩T2′.Claim 18.
B¯1∩B¯2≠∅.Proof.
Otherwise, assume thatB¯1∩B¯2=∅. Notice that Nx∩B¯1≠∅ and Nx∩B¯2≠∅, and we see that Nx∩B¯1∩T2′≠∅ and Nx∩B¯2∩T1′≠∅ since GNx−x1,x2,x3≅K2. Without the loss of generality, let x4∈B¯2∩T1′. Furthermore, we see that Nx∩B¯1∩B2=∅ and Nx∩B¯2∩B1=∅. If B1∩B¯2≠∅, then Lemma 1 assures us that B¯1∩B2=∅. It follows that B¯1∩T2′≥B¯1≥3. Now, Lemma 1 assures us that B¯2∩T1′≥B¯1∩T2′≥3 and B2∩T1′≥B¯1∩T2′≥3. This implies that T1′≥6, a contradiction.
Thus, we may assume thatB1∩B¯2=∅ and, similarly, B¯1∩B2=∅. Similar to the argument of the last paragraph, we have B¯1≥3 and B¯2≥3. It follows that B2∩T1′≥B¯1∩T2′≥3 and B¯2∩T1′≥B¯1∩T2′≥3. Hence, T1′≥6, a contradiction. Hence, Claim 18 holds.
By Claim18 and Lemma 1, we see that B1∩B2 is a fragment and NB1∩B2∩x1,x,x2,x3=x1,x,x3. Now, Claim 16 implies that B1∩B2=x2. Therefore, w1,w2⊆B1∪T1′. If B1∪T1′≤8, it follows that Nx3⊆B1∪T1′−x4,x1,y1,y2, which implies that dx3≤4, a contradiction. So, we may assume that B1∪T1′≥9. Similarly, we may assume that B2∪T2′≥9.Claim 19.
B1∩B¯2=∅ and B2∩B¯1=∅.Proof.
Clearly,B¯1∩B¯2 is a fragment. It follows that Nx∩B¯1∩B¯2≠∅. Hence, Nx∩B¯1∩B2=∅ and Nx∩B¯2∩B1=∅, since GNx−x1,x2,x3≅K2.
Now, ifB1∩B¯2≠∅, then the fact Nx∩B¯1∩B2=∅ assures us that B2∩B¯1=∅. Notice that B2∪T2′≥9 and B1∩B2=x2, and we have B2∩T1′≥3.
Now, Lemma1 assures us that B1∩T2′≥B2∩T1′≥3 and B¯1∩T2′≥B2∩T1′≥3. Hence, T2′≥6, a contradiction. This contradiction implies that B1∩B¯2=∅. Similarly, B2∩B¯1=∅.
Now, we are ready to complete the proof of Case1. Notice that B2∪T2′≥9, B1∩B2=x2, and B2∩B¯1=∅, and we see that B2∩T1′|≥3. Similarly, B1∩T2′|≥3. Now, Lemma 1 assures us that B¯1∩T2′≥B2∩T1′≥3. It follows that T2′≥6, a contradiction.Case 2.
T2′∩x1,x,x2,x3=x1,x2.
It follows thatT2′=5. Let B2 be a T2′-fragment. Without the loss of generality, suppose x,x3⊆B2. Now, we see that x3∈B1∩B2, x∈T1′∩B2, x2∈T2′∩B1, and x1∈T1′∩T2′.Claim 20.
B¯1∩B¯2≠∅.Proof.
SupposeB¯1∩B¯2=∅. If B1∩B¯2=∅, then B¯2∩T1′=B¯2≥3. Now, Lemma 1 assures us that B1∩T2′≥B¯2∩T1′≥3. This implies that B¯1∩T2′≤2, which implies that B¯1∩T2′≥B¯2∩T1′. Now, Lemma 1 assures us that B¯1∩B2=∅, which implies that B¯1≤2, a contradiction.
Thus, we may assume thatB1∩B¯2≠∅. Similarly, B¯1∩B2≠∅. Thus, both B1∩B¯2 and B¯1∩B2 are fragments of G. Without loss of generality, we may assume y1∈B1∩B¯2. Therefore, y3∈B¯1∩B2 and y2∈T1′∩T2′. Notice that GNy2−x1,y1,y3≅K2, and then either Ny2∩B1∩B¯2=1 or Ny2∩B¯1∩B2=1. Without the loss of generality, let Ny2∩B1∩B¯2=1. Now, we find that Nx1,y2∩B1∩B¯2=y1. Now, Lemma 2 assures us that B1∩B¯2=y1. Thus, y1x2∈EG. This contradicts the fact that G has type 3.
Now, we are ready to complete the proof of Case2. By Claim 20, we have that B1∩B2 is a fragment, and NB1∩B2∩x1,x,x2,x3=x,x1,x2. This contradicts Claim 16.Lemma 14.
LetG be a TCC-5-connected graph such that VG≥10. If G has type 4, then G can be reduced to a 5-connected H such that 0<VG−VH<3.Proof.
Letx be a vertex of G such that Nx=x1,…,x5. Let x1x2x3x4x5 be a path of G. Now, Lemma 10 assures us that G does not contain K4. By Lemma 9, every fragment of G has cardinality one or at least four.Claim 21.
EitherNx2∩Nx3=x or Nx3∩Nx4=x.Proof.
SupposeNx2∩Nx3≥2 and Nx3∩Nx4≥2. Let Nx3=z1,z2,x4,x,x2 and Nx2=w1,x1,x,x2,z1, where z2x4∈EG. If w1x1∉EG, then GNx1 has at least two components, a contradiction. Thus, w1x1∈EG. Let Nx1=t1,t2,w1,x2,x. We may assume t1t2w1x2x is the path of GNx1. Now, we see that Nx2∩Nw1=x1. Let g∈AutG such that gx=x1. It follows that gNx is a map from Nx to Nx1. It follows that either gx1=x or gx1=t1.
Ifgx1=x, then gx2=x2,gx3=w1,gx4=t2,andgx5=t1. Now, since Nx2∩Nx3≥2, we see that Nx2∩Nw1≥2, a contradiction. So, we may assume that gx1=t1. It follows that gx2=t2,gx3=w1,gx4=x2,gx5=x1. Now, since Nx3∩Nx4≥2, we see that Nx2∩Nw1≥2, a contradiction.
Now, by symmetry, assume thatNx2∩Nx3=x. Let Nx2=y1,y2,x1,x,x3 and Nx3=z1,z2,x4,x,x2. Furthermore, let y1y2x1xx3 and z1z2x4xx2 be the paths of GNx2 and GNx3, respectively. Hence, we may let Nx1=w1,w2,y2,x2,x, and w1w2y2x2x is the path of GNx1. Furthermore, we have Nx2∩Nx3=1 and Nx3∩Nx4=2.
LetG0=G/xx1,x2x3. Lemma 11 assures us that κG0≥4. Suppose κG0=4. Let T′ be a smallest separator of G0. Clearly, we observe that xx1,x2x3∩T′≠∅.Claim 22.
xx1,x2x3⊆T′.Proof.
Supposexx1∉T′. Let T0=T′∪x2,x3−x2x3. Then, T0 is a smallest separator of G. Let A be a fragment of T0 which contains x,x1. It follows that A≥2. Now, Lemma 9 shows that A¯=1. Clearly, A¯⊆Nx2∩Nx3. Now, since x∈A, we see that Nx2∩Nx3=2, which is a contradiction. Hence, we may assume that xx1∈T′. If x2x3∉T′, let T0=T′∪x,x1−xx1. Then, T0 is smallest separator G. Let B be a T0-fragment which contains x2,x3. It follows that B≥2. Now, Lemma 9 shows that B¯=1. Clearly, B¯⊆x4,x5. Hence, x1 is adjacent to either x4 or x5, a contradiction. Hence, x2x3∈T′.
LetT0=T′∪x,x1,x2,x3−xx1,x2x3. Let A be a component of G−T0, A′=G−T0−A. As x4x5∈EG, Nx∩A=∅ or Nx∩A′=∅. Similarly, Nx2∩A=∅ or Nx2∩A′=∅. Without the loss of generality, let Nx∩A=∅. Then, Nx2∩A′=∅ and Nx2∩A≠∅, Nx∩A′≠∅.
Hence,T=T0−x is a smallest separator of G. Let A be a T−fragment. Clearly, A¯=A′∪x. This implies that A¯≥2. Now, Lemma 9 shows that A=1. So, A⊆Nx2∩Nx3. Recall that x∈A¯, and we find that Nx2∩Nx3≥2. This contradicts the fact that Nx2∩Nx3=x.



---

*Source: 9315494-2020-07-09.xml*