The k-subconnectedness of planar graphs

1.   Introduction and terminology

Connectivity is an important property of graphs. It has been extensively studied (see ^[1]). A graph $G = (V, E)$ is called k-connected $(k\geq 1)$ (k-edge-connected) if, for any subset $S\subseteq V(G)$ ($S\subseteq E(G)$) with $|S| < k$, $G-S$ is connected. The connectivity $\kappa (G)$ (edge connectivity $\lambda (G)$) is the order (size) of minimum cutset (edge cutset) $S\subseteq V(G)$ ($S\subseteq E(G)$). When $G$ is a complete graph $K_{n}$, we define that $\kappa (G) = n-1$.

In recent years, conditional connectivities attract researchers' attention. For example, Peroche ^[2] studied several sorts of connectivities, including cyclic edge (vertex) connectivity, and their relations. A cyclic edge (vertex) cutset $S$ of $G$ is an edge (vertex) cutset whose deletion disconnects $G$ such that at least two of the components of $G-S$ contain a cycle respectively. The cyclic edge (vertex) connectivity, denoted by $c\lambda (G)$ ($c\kappa (G)$), is the cardinality of a minimum cyclic edge (vertex) cutset of $G$. Dvoŕǎk, Kára, Král and Pangrác ^[3] obtained the first efficient algorithm to determine the cyclic edge connectivity of cubic graphs. Lou and Wang ^[4] obtained the first efficient algorithm to determine the cyclic edge connectivity for k-regular graphs. Then Lou and Liang ^[5] improved the algorithm to have time complexity $O(k^{9}V^{6})$. Lou ^[6] also obtained a square time algorithm to determine the cyclic edge connectivity of planar graphs. In ^[7], Liang, Lou and Zhang obtained the first efficient algorithm to determine the cyclic vertex connectivity of cubic graphs. Liang and Lou ^[8] also showed that there is an efficient algorithm to determine the cyclic vertex connectivity for k-regular graphs with any fixed $k$.

Another related concept is $linkage$. Let $G$ be a graph with at least $2k$ vertices. If, for any $2k$ vertices $u_{1}, u_{2}, \cdots, u_{k}, v_{1}, v_{2}, \cdots, v_{k}$, there are $k$ disjoint paths $P_{i}$ from $u_{i}$ to $v_{i} \; (i = 1, 2, \cdots, k)$ in $G$, then $G$ is called k-linked. Thomassen ^[9] mentioned that a necessary condition for $G$ to be k-linked is that $G$ is ($2k-1$)-connected. But this condition is not sufficient unless $k = 1$. He also gave a complete characterization of 2-linked graphs. Bollobás and Thomason ^[10] proved that if $\kappa (G) \geq 22k$, then $G$ is k-linked. Kawarabayashi, Kostochka and Yu ^[11] proved that every 2k-connected graph with average degree at least $12k$ is k-linked.

In ^[12], Qin, Lou, Zhu and Liang introduced the new concept of k-subconnected graphs. Let $G$ be a graph with at least $2k$ vertices. If, for any $2k$ vertices $v_{1}, v_{2}, \cdots, v_{2k}$ in $G$, there are $k$ vertex-disjoint paths joining $v_{1}, v_{2}, \cdots, v_{2k}$ in pairs, then $G$ is called k-subconnected. If $G$ is k-subconnected and $\nu (G) \geq 3k-1$, then $G$ is called a properly k-subconnected graph. In ^[12], Qin et al. showed that a properly k-subconnected graph is also a properly ($k-1$)-subconnected graph. But only when $\nu (G) \geq 3k-1$, that $G$ is k-subconnected implies that $G$ is ($k-1$)-subconnected. Qin et al. ^[12] also gave a sufficient condition for a graph to be k-subconnected and a necessary and sufficient condition for a graph to be a properly k-subconnected graph (see Lemmas 1 and 2 and Corollary 3 in this paper).

If $G$ has at least $2k$ vertices, that $G$ is k-linked implies that $G$ is k-connected, while that $G$ is k-connected implies that $G$ is k-subconnected (see Lemma 6 in this paper). Also in a k-connected graph $G$, deleting arbitrarily some edges from $G$, the resulting graph $H$ is still k-subconnected. So a graph $H$ to be k-subconnected is a spanning substructure of a k-connected graph $G$. To study k-subconnected graphs may help to know more properties in the structure of k-connected graphs. Notice that a k-connected graph may have a spanning substructure to be m-subconnected for $m > k$.

K-subconnected graphs have some background in matching theory. The proof of the necessary and sufficient condition ^[12] for properly k-subconnected graphs uses similar technique to matching theory.

Let $S$ be a subset of $V(G)$ of a graph $G$. We denote by $G[S]$ the induced subetaaph of $G$ on $S$. We also denote by $\omega (G)$ the number of components of G. We also use $\nu(G)$ and $\varepsilon (G)$ to denote $|V(G)|$ and $|E(G)|$. If $G$ is a planar graph, we denote by $\phi (G)$ the number of faces in the planar embedding of $G$. Let $H$ be a graph. A subdivision of $H$ is a graph $H'$ obtained by replacing some edges by paths respectively in $H$. For other terminology and notation not defined in this paper, the reader is referred to ^[13].

2.   Preliminary results

In this section, we shall present some known results and some straightforward corollaries of the known results which will be used in the proof of our main theorems.

Lemma 1 (Theorem 1 of ^[12]). Let $G$ be a connected graph with at least $2k$ vertices. Then $G$ is k-subconnected if, for any cutset $S \subseteq V(G)$ with $|S|\leq k-1$, $\omega (G-S)\leq |S|+1$.

Lemma 2 (Theorem 2 of ^[12]). Let $G$ be a connected graph with at least $3k-1$ vertices. If $G$ is a properly k-subconnected graph, then, for any cutset $S\subseteq V(G)$ with $|S|\leq k-1$, $\omega (G-S)\leq |S|+1$.

Only when $v \geq 3k-1$, that $G$ is k-subconnected implies that $G$ is (k-1)-subconnected. Here is an counterexample. Let $S = K_{k-2}$ be a complete graph of $k-2$ vertices, let $H$ be $k$ copies of $K_{2}$, and let $G$ be a graph with $V(G) = V(S) \cup V(H)$ and $E(G) = E(S) \cup E(H) \; \cup \; \{uv | u \in V(S), v \in V(H)\}$. Then $v(G) = 3k-2$, and $G$ is not (k-1)-subconnected since we can choose 2($k$-1) vertices by taking one vertex from each copy of $K_{2}$ in $H$ and taking all vertices of $S$, then these 2($k$-1) vertices cannot be joined by $k$-1 independent paths in pairs. But $G$ is k-subconnected since when we take any 2$k$ vertices from $G$, some pairs of vertices will be taken from several same $K_{2}$ 's in $H$, and then the 2$k$ vertices can be joined by $k$ independent paths in pairs.

Corollary 3 (Theorem 3 of ^[12]). Let $G$ be a connected graph with at least $3k-1$ vertices. Then $G$ is a properly k-subconnected graph if and only if, for any cutset $S\subseteq V(G)$ with $|S|\leq k-1$, $\omega (G-S)\leq |S|+1$.

Lemma 4 (^[14]). Every 4-connected planar graph is Hamiltonian.

Lemma 5. If a graph $G$ has a Hamilton path, then $G$ is k-subconnected for each $k$ such that $1\leq k\leq \nu(G)/2$.

Proof. Let $P$ be a Hamilton path in $G$. Let $v_{i}$, $i = 1, 2, \cdots, 2k$, be any $2k$ vertices in $V(G)$. Without loss of generality, assume that $v_{1}, v_{2}, \cdots, v_{2k}$ appear on $P$ in turn. Then there are $k$ paths $P_{i}$ on $P$ from $v_{2i-1}$ to $v_{2i}$, $i = 1, 2, \cdots, k$, respectively. So $G$ is k-subconnected.

Lemma 6. A k-connected graph $G$ with at least $2k$ vertices is k-subconnected.

Proof. Let $G$ be a k-connected graph with at least $2k$ vertices. Then $G$ does not have a cutset $S\subseteq V(G)$ with $|S|\leq k-1$, so the statement that, for any cutset $S\subseteq V(G)$ with $|S|\leq k-1$, $\omega (G-S)\leq |S|+1$ is true. By Lemma 1, $G$ is k-subconnected.

3.   The k-subconnectedness of planar graphs

In this section, we shall show the k-subconnectedness of planar graphs with different connectivities, and show the bounds of k-subconnectedness are sharp.

Corollary 7. A 1-connected planar graph $G$ with at least 2 vertices is 1-subconnected.

Proof. By Lemma 6, the result follows.

Corollary 8. A 2-connected planar graph $G$ with at least 4 vertices is 2-subconnected.

Proof. By Lemma 6, the result follows.

Theorem 9. A 4-connected planar graph $G$ is k-subconnected for each $k$ such that $1\leq k\leq \nu (G)/2$.

Proof. By Lemma 4, $G$ has a Hamilton cycle $C$, and then has a Hamilton path $P$. By Lemma 5, the result follows.

Theorem 10. A 3-connected planar graph $G$ with at least $2k$ vertices is k-subconnected for $k = 4, 5, 6$.

Proof. Suppose that $G$ is a 3-connected planar graph with at least $2k$ vertices which is not k-subconnected. By Lemma 1, there is a cutset $S\subseteq V(G)$ with $|S|\leq k-1\leq$ such that $\omega (G-S)\geq |S|+2$. Since $G$ is 3-connected, there is no cutset with less than 3 vertices and so $|S|\geq 3$. On the other hand, $k = 4, 5, 6$, so $|S|\leq 5$. Thus let us consider three cases.

In the first case, $|S| = 3$. By our assumption, $\omega(G-S)\geq |S|+2$, let $C_{1}, C_{2}, \cdots, C_{5}$ be different components of $G-S$, and $S = \{ x_{1}, x_{2}, x_{3}\}$. Since $G$ is 3-connected, every $C_{i}$ is adjacent to each $x_{j}$ ($1\leq i\leq 5, 1\leq j\leq 3$). Contract every $C_{i}$ to a vertex $C_{i}^{'}$ ($i = 1, 2, \cdots, 5$) to obtain a planar graph $G'$ as $G$ is planar. Then $G'[\{ x_{1}, x_{2}, x_{3}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}\}]$ contains a $K_{3, 3}$, which contradicts the fact that $G'$ is a planar graph.

In the second case, $|S| = 4$. By our assumption, $\omega(G-S)\geq |S|+2$, let $C_{1}, C_{2}, \cdots, C_{6}$ be different components of $G-S$ and $S = \{ x_{1}, x_{2}, x_{3}, x_{4}\}$. Contract every $C_{i}$ to a vertex $C_{i}^{'}$ ($i = 1, 2, \cdots, 6$) to obtain a planar graph $G'$ as $G$ is planar. Since $G$ is 3-connected, each $C_{i}^{'}$ is adjacent to at least 3 vertices in $S$ ($1\leq i\leq 6$). (In the whole proof, we shall consider that $C_{i}^{'}$ is adjacent to only 3 vertices in $S$, and we shall neglect other vertices in $S$ which are possibly adjacent to $C_{i}^{'}$). Since the number of 3-vertex-combinations in $S$ is $C(4, 3) = 4$, but $C_{1}^{'}, C_{2}^{'}, \cdots, C_{6}^{'}$ have 6 vertices, by the Pigeonhole Principle, there are two vertices in $\{ C_{1}^{'}, C_{2}^{'}, \cdots, C_{6}^{'}\}$ which are adjacent to the same three vertices in $S$. Without loss of generality, assume that $C_{1}^{'}$ and $C_{2}^{'}$ are both adjacent to $x_{1}, x_{2}, x_{3}$. If there is another $C_{i}^{'}$ ($3\leq i\leq 6$) adjacent to $x_{1}, x_{2}, x_{3}$, say $C_{3}^{'}$, then $G'[\{ x_{1}, x_{2}, x_{3}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}\}]$ contains a $K_{3, 3}$, which contradicts the fact that $G'$ is planar (which also contradicts the assumption that $G$ is a planar graph because $G$ has a subetaaph which can be contracted to a $K_{3, 3}$). So $C_{i}^{'}$ cannot be adjacent to $x_{1}, x_{2}, x_{3}$ at the same time ($i = 3, 4, 5, 6$).

Suppose $C_{3}^{'}$ is adjacent to $x_{2}, x_{3}, x_{4}$. If one of $C_{4}^{'}, C_{5}^{'}, C_{6}^{'}$ is adjacent to both $x_{1}$ and $x_{4}$, say $C_{4}^{'}$, then $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{4}^{'}x_{1}$, so $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}\}]$ contains a subdivision of $K_{3, 3}$, contradicting the fact that $G'$ is planar. Since $C_{4}^{'}, C_{5}^{'}, C_{6}^{'}$ are all not adjacent to $x_{1}, x_{2}, x_{3}$ at the same time, they are all adjacent to $x_{4}$. But each of them cannot be adjacent to both $x_{1}$ and $x_{4}$. So they are all not adjacent to $x_{1}$. Hence $C_{4}^{'}, C_{5}^{'}, C_{6}^{'}$ are all adjacent to $x_{2}, x_{3}, x_{4}$ at the same time. Then $G'[\{ x_{2}, x_{3}, x_{4}\} \cup \{ C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a $K_{3, 3}$, contradicting the fact that $G'$ is a planar graph.

The cases that $C_{3}^{'}$ is adjacent to $x_{1}, x_{3}, x_{4}$ or $x_{1}, x_{2}, x_{4}$ are similar.

In the third case, $|S| = 5$. By our assumption, $\omega(G-S)\geq |S|+2$, let $C_{1}, C_{2}, \cdots, C_{7}$ be different components of $G-S$ and $S = \{ x_{1}, x_{2}, \cdots, x_{5}\}$. Since $G$ is planar, contracting $C_{i}$ to a vertex $C_{i}^{'}$ ($i = 1, 2, \cdots, 7$), we obtain a planar graph $G'$. Also since $G$ is 3-connected, every $C_{i}^{'}$ is adjacent to at least 3 vertices in $S$ ($1\leq i\leq 7$).

Case 1. There are two of $C_{i}^{'}$ ($i = 1, 2, \cdots, 7$) adjacent to the same three vertices in $S$. Without loss of generality, assume that $C_{1}^{'}$ and $C_{2}^{'}$ are both adjacent to $x_{1}, x_{2}, x_{3}$ at the same time.

If there is another vertex $C_{i}^{'}$ ($3\leq i\leq 7$) adjacent to $x_{1}, x_{2}, x_{3}$ at the same time, say $C_{3}^{'}$. Then $G'[\{x_{1}, x_{2}, x_{3}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}\}]$ contains a $K_{3, 3}$, contradicting the fact that $G'$ is planar. So $C_{3}^{'}$ cannot be adjacent to $x_{1}, x_{2}, x_{3}$ at the same time. Without loss of generality, we have two subcases.

Suppose $C_{3}^{'}$ is only adjacent to two vertices in $\{x_{1}, x_{2}, x_{3}\}$, say $x_{2}$ and $x_{3}$. Then $C_{3}^{'}$ must be adjacent to one of $x_{4}$ and $x_{5}$ as $G$ is 3-connected. Without loss of generality, assume that $C_{3}^{'}$ is also adjacent to $x_{4}$. If one of $C_{i}^{'}$ ($i = 4, 5, 6, 7$) is adjacent to both $x_{1}$ and $x_{4}$, say $C_{4}^{'}$. Then $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{4}^{'}x_{1}$, hence $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}\}]$ contains a subdivision of $K_{3, 3}$, contradicting the fact that $G'$ is planar. So none of $C_{i}^{'}$ ($i = 4, 5, 6, 7$) is adjacent to both $x_{1}$ and $x_{4}$.

Case (1.1). Suppose that $C_{4}^{'}$ is adjacent to three vertices in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$ .

If $C_{4}^{'}$ is adjacent to $x_{1}, x_{2}, x_{3}$ at the same time, then the case is similar to that $C_{3}^{'}$ is adjacent to $x_{1}, x_{2}, x_{3}$ at the same time, and we have a contradiction. So $C_{4}^{'}$ is not adjacent to $x_{1}, x_{2}, x_{3}$ at the same time. If $C_{4}^{'}$ is adjacent to $x_{1}$, since $C_{4}^{'}$ is adjacent to three vertices in $\{x_{1}, x_{2}, x_{3}, x_{4}\}$ but not $x_{1}, x_{2}, x_{3}$, so $C_{4}^{'}$ is adjacent to $x_{1}$ and $x_{4}$, by the argument above, we have a contradiction. Hence $C_{4}^{'}$ can be adjacent only to $x_{2}, x_{3}, x_{4}$.

Now $x_{1}$ and $x_{4}$ are symmetric, while $x_{2}$ and $x_{3}$ are symmetric in $G^{'} \left[\{x_{1}, x_{2}, x_{3}, x_{4}\} \cup \{C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}\} \right]$. Then $C_{i}^{'}(i = 5, 6, 7)$ must be adjacent to $x_{5}$, we have two cases as follows.

Notice that now there are not $i$ and $j$, $5 \leq i \neq j\leq 7$, such that $C_{i}^{'}$ is adjacent to $x_{1}$ and $C_{j}^{'}$ is adjacent to $x_{4}$, otherwise $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{j}^{'}x_{5}C_{i}^{'}x_{1}$, then $G^{'} \left[\{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{i}^{'}, C_{j}^{'}\}\right]$ contains a subdivision of $K_{3, 3}$, contrary to the fact that $G^{'}$ is planar.

Suppose $C_{5}^{'}$ is adjacent to $x_{3}, x_{4}, x_{5}$. If $C_{6}^{'}$ is also adjacent to $x_{3}, x_{4}, x_{5}$, then $C_{7}^{'}$ cannot be adjacent to $x_{3}, x_{4}, x_{5}$, otherwise $G'[\{ x_{3}, x_{4}, x_{5}\} \cup \{ C_{5}^{'}, C_{6}^{'}, C_{7}^{'}\}]$ contains a $K_{3, 3}$, a contradiction. So suppose $C_{7}^{'}$ is adjacent to $x_{2}, x_{4}, x_{5}$, then $C_{7}^{'}$ is connected to $x_{3}$ by path $C_{7}^{'}x_{2}C_{2}^{'}x_{3}$, and then $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{2}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. So suppose $C_{7}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$. But $C_{7}^{'}$ is connected to $x_{4}$ by path $C_{7}^{'}x_{2}C_{3}^{'}x_{4}$, then $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{3}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction again. If $C_{6}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$, suppose $C_{7}^{'}$ is adjacent to $x_{3}, x_{4}, x_{5}$, then this case is similar to that $C_{6}^{'}$ is adjacent to $x_{3}, x_{4}, x_{5}$ and $C_{7}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$. Then suppose $C_{7}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$. Now $C_{3}^{'}$ is connected to $x_{5}$ by path $C_{3}^{'}x_{4}C_{5}^{'}x_{5}$, so $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{3}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now suppose $C_{7}^{'}$ is adjacent to $x_{2}, x_{4}, x_{5}$. Then $C_{6}^{'}$ is connected to $x_{4}$ by path $C_{6}^{'}x_{5}C_{7}^{'}x_{4}$, hence $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{3}^{'}, C_{4}^{'}, C_{6}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. The remaining case is that $C_{6}^{'}$ is adjacent to $x_{2}, x_{4}, x_{5}$. Now the cases that $C_{7}^{'}$ is adjacent to $x_{2}, x_{4}, x_{5}$ and that $C_{7}^{'}$ is adjacent to $x_{3}, x_{4}, x_{5}$ are symmetric, we only discuss the former. Then $C_{5}^{'}$ is connected to $x_{2}$ by path $C_{5}^{'}x_{3}C_{4}^{'}x_{2}$, so $G^{'} \left[\{x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{C_{4}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}\} \right]$ contains a subdivision of $K_{3, 3}$, a contradiction. The remaining case is that $C_{7}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$. Now $C_{7}^{'}$ is connected to $x_{4}$ by path $C_{7}^{'} x_{5} C_{6}^{'} x_{4}$. Hence $G^{'} \left[\{x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{C_{3}^{'}, C_{4}^{'}, C_{6}^{'}, C_{7}^{'}\} \right]$ contains a subdivision of $K_{3, 3}$, a contradiction.

Suppose $C_{5}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$. If $C_{6}^{'}$ and $C_{7}^{'}$ are both adjacent to $x_{2}, x_{3}, x_{5}$, then $G^{'} \left[\{ x_{2}, x_{3}, x_{5}\} \cup \{C_{5}^{'}, C_{6}^{'}, C_{7}^{'} \}\right]$ contains a $K_{3, 3}$, contradicting the fact that $G^{'}$ is planar. So one of $C_{5}^{'}$, $C_{6}^{'}$, $C_{7}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$, the other two are adjacent to $x_{3}, x_{4}, x_{5}$; or one of $C_{5}^{'}$, $C_{6}^{'}$, $C_{7}^{'}$ is adjacent to $x_{3}, x_{4}, x_{5}$, the other two are adjacent to $x_{2}, x_{3}, x_{5}$; or $C_{5}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$, $C_{6}^{'}$ is adjacent to $x_{3}, x_{4}, x_{5}$ and $C_{7}^{'}$ is adjacent to $x_{2}, x_{4}, x_{5}$. These three cases are symmetric to cases discussed above. (Notice that the roles of $C_{5}^{'}$, $C_{6}^{'}$ and $C_{7}^{'}$ are symmetric.)

Case (1.2). Now suppose $\{ x_{2}, x_{3}, x_{4}\}$ - $N(C_{4}^{'}) \; \neq \; \varnothing$.

Notice that $\{ x_{2}, x_{3}, x_{4}\}$ - $N(C_{i}^{'}) \; \neq \; \varnothing$ for $5\leq i\leq 7$, otherwise the $C_{i}^{'}$ ($5\leq i\leq 7$) is similar to $C_{4}^{'}$ as discussed above, and the other three in $\{ C_{4}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}\}$ are similar to $C_{5}^{'}, C_{6}^{'}, C_{7}^{'}$, by the same argument as above, we obtain a contradiction. Also since $C_{4}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}$ each cannot be adjacent to both $x_{1}$ and $x_{4}$, all of $C_{4}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}$ must be adjacent to $x_{5}$. Now $x_{1}$ and $x_{4}$ are not symmetric but $x_{2}$ and $x_{3}$ are symmetric in $G'[\{x_{1}, x_{2}, x_{3}, x_{4}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}\}]$.

First, suppose $C_{4}^{'}$ is adjacent to $x_{4}$ and $x_{3}$ besides $x_{5}$. Then suppose $C_{5}^{'}$ is adjacent to $x_{4}$ and $x_{3}$. If $C_{6}^{'}$ is also adjacent to $x_{4}$ and $x_{3}$, then $G'[\{ x_{3}, x_{4}, x_{5}\} \cup \{ C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains $K_{3, 3}$, a contradiction. Then suppose $C_{6}^{'}$ is adjacent to $x_{4}, x_{2}$, now $C_{6}^{'}$ is connected to $x_{3}$ by path $C_{6}^{'}x_{2}C_{2}^{'}x_{3}$, and $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{2}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now suppose $C_{6}^{'}$ is adjacent to $x_{4}, x_{1}$, then $C_{6}^{'}$ is connected to $x_{3}$ by path $C_{6}^{'}x_{1}C_{2}^{'}x_{3}$, and $G'[\{ x_{1}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{2}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$ a contradiction. Then suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{2}$. Now $C_{6}^{'}$ is connected to $x_{4}$ by path $C_{6}^{'}x_{2}C_{3}^{'}x_{4}$, so $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{3}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Next we suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{1}$, then $C_{6}^{'}$ is connected to $x_{2}$ by path $C_{6}^{'}x_{5}C_{4}^{'}x_{4}C_{3}^{'}x_{2}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Then suppose $C_{6}^{'}$ is adjacent to $x_{2}, x_{1}$, now $C_{6}^{'}$ is connected to $x_{3}$ by path $C_{6}^{'}x_{5}C_{4}^{'}x_{3}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now we suppose $C_{5}^{'}$ is adjacent to $x_{4}, x_{2}$. By the symmetry of the roles of $C_{4}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}$, we only consider the cases of $C_{6}^{'}$ as follows. Suppose $C_{6}^{'}$ is adjacent to $x_{4}, x_{2}$. Then $C_{4}^{'}$ is connected to $x_{2}$ by path $C_{4}^{'}x_{3}C_{3}^{'}x_{2}$, and $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{3}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Then suppose $C_{6}^{'}$ is adjacent to $x_{4}, x_{1}$. Now $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{6}^{'}x_{1}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{2}$. Then we consider $C_{7}^{'}$. By the symmetry of the roles of $C_{7}^{'}$ and $C_{6}^{'}$, we only consider the cases that $C_{7}^{'}$ is adjacent to $\{ x_{3}, x_{2}\}, \{ x_{3}, x_{1}\}, \{ x_{2}, x_{1}\}$ respectively. If $C_{7}^{'}$ is adjacent to $x_{3}, x_{2}$, then $C_{5}^{'}$ is connected to $x_{3}$ by path $C_{5}^{'}x_{4}C_{4}^{'}x_{3}$, and $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{4}^{'}, C_{5}^{'}, C_{6}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. If $C_{7}^{'}$ is adjacent to $x_{3}, x_{1}$, then $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{5}^{'}x_{5}C_{7}^{'}x_{1}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{5}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. If $C_{7}^{'}$ is adjacent to $x_{2}, x_{1}$, then $C_{7}^{'}$ is connected to $x_{3}$ by path $C_{7}^{'}x_{5}C_{4}^{'}x_{3}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{4}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{1}$. Then $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{4}^{'}x_{5}C_{6}^{'}x_{1}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now we suppose $C_{6}^{'}$ is adjacent to $x_{2}, x_{1}$. Then $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{4}^{'}x_{5}C_{6}^{'}x_{1}$, and $G'[\{x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now suppose $C_{5}^{'}$ is adjacent to $x_{4}, x_{1}$. Then $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{4}^{'}x_{5}C_{5}^{'}x_{1}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{5}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Then we suppose $C_{5}^{'}$ is adjacent to $x_{3}, x_{2}$. By symmetry of $C_{5}^{'}$ and $C_{6}^{'}$, we only need to consider the following cases. Suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{2}$. Then $C_{3}^{'}$ is connected to $x_{5}$ by path $C_{3}^{'}x_{4}C_{4}^{'}x_{5}$, and $G'[\{ x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{3}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{1}$, then $C_{3}^{'}$ is connected to $x_{1}$ by path $C_{3}^{'}x_{4}C_{4}^{'}x_{5}C_{6}^{'}x_{1}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Then suppose $C_{6}^{'}$ is adjacent to $x_{2}, x_{1}$, by the same argument as last case, we also obtain a contradiction. Now we suppose $C_{5}^{'}$ is adjacent to $x_{3}, x_{1}$. Then $C_{5}^{'}$ is connected to $x_{2}$ by path $C_{5}^{'}x_{5}C_{4}^{'}x_{4}C_{3}^{'}x_{2}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{5}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. So suppose $C_{5}^{'}$ is adjacent to $x_{2}, x_{1}$. Then $C_{5}^{'}$ is connected to $x_{3}$ by path $C_{5}^{'}x_{5}C_{4}^{'}x_{3}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{4}^{'}, C_{5}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Since the case that $C_{4}^{'}$ is adjacent to $x_{4}, x_{2}$ is symmetric to the case that $C_{4}^{'}$ is adjacent to $x_{4}, x_{3}$, we do not discuss this case. The case that $C_{4}^{'}$ is adjacent to $x_{4}, x_{1}$ is excluded by the discussion before Case (1.1). So we suppose $C_{4}^{'}$ is adjacent to $x_{3}, x_{2}$ now. By symmetry, we only need to consider the following cases. Suppose $C_{5}^{'}$ is adjacent to $x_{3}, x_{2}$, then suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{2}$. Then $G'[\{ x_{2}, x_{3}, x_{5}\} \cup \{ C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a $K_{3, 3}$, a contradiction. Then suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{1}$. Now $C_{6}^{'}$ is connected to $x_{2}$ by path $C_{6}^{'}x_{1}C_{1}^{'}x_{2}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{5}\} \cup \{ C_{1}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. So suppose that $C_{6}^{'}$ is adjacent to $x_{2}, x_{1}$, then $C_{6}^{'}$ is connected to $x_{3}$ by path $C_{6}^{'}x_{1}C_{1}^{'}x_{3}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{5}\} \cup \{ C_{1}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Now suppose $C_{5}^{'}$ is adjacent to $x_{3}, x_{1}$, then suppose $C_{6}^{'}$ is adjacent to $x_{3}, x_{1}$. Then $C_{4}^{'}$ is connected to $x_{1}$ by path $C_{4}^{'}x_{2}C_{1}^{'}x_{1}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{5}\} \cup \{ C_{1}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. So suppose $C_{6}^{'}$ is adjacent to $x_{2}, x_{1}$. Now $C_{6}^{'}$ is connected to $x_{3}$ by path $C_{6}^{'}x_{5}C_{4}^{'}x_{3}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Then suppose $C_{5}^{'}$ is adjacent to $x_{2}, x_{1}$, and $C_{6}^{'}$ can be adjacent only to $x_{2}, x_{1}$, by the same argument as last case, we can obtain a contradiction. Now suppose $C_{4}^{'}$ is adjacent to $x_{3}, x_{1}$, then suppose $C_{5}^{'}$ and $C_{6}^{'}$ are both adjacent to $x_{3}, x_{1}$. But $G'[\{ x_{1}, x_{3}, x_{5}\} \cup \{ C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains $K_{3, 3}$, a contradiction. So we suppose $C_{6}^{'}$ is adjacent to $x_{2}, x_{1}$ subject to the above assumption of $C_{4}^{'}$ and $C_{5}^{'}$. Now $C_{6}^{'}$ is connected to $x_{3}$ by path $C_{6}^{'}x_{5}C_{4}^{'}x_{3}$, and $G'[\{ x_{1}, x_{2}, x_{3}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. Then suppose $C_{5}^{'}$ is adjacent to $x_{2}, x_{1}$. Substituting $C_{5}^{'}$ for $C_{6}^{'}$ in the discussion of last case, we can obtain a contradiction. The remaining case is that $C_{4}^{'}, C_{5}^{'}, C_{6}^{'}$ are all adjacent to $x_{2}, x_{1}$. Then $G'[\{ x_{1}, x_{2}, x_{5}\} \cup \{ C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains $K_{3, 3}$, a contradiction.

Now we come back to the discussion of the first paragraph in Case 1. We have the second subcase as follows.

Suppose $C_{3}^{'}$ is adjacent to only one vertex in $\{x_{1}, x_{2}, x_{3}\}$. By the symmetry of the roles of $C_{3}^{'}, C_{4}^{'}, \cdots, C_{7}^{'}$, we can assume that each of $C_{3}^{'}, C_{4}^{'}, \cdots, C_{7}^{'}$ is adjacent to only one vertex in $\{ x_{1}, x_{2}, x_{3}\}$. So all of $C_{3}^{'}, C_{4}^{'}, \cdots, C_{7}^{'}$ are adjacent to both $x_{4}$ and $x_{5}$, and one of $x_{1}, x_{2}, x_{3}$. But $x_{1}, x_{2}, x_{3}$ have only 3 vertices and $C_{3}^{'}, C_{4}^{'}, \cdots, C_{7}^{'}$ have 5 vertices, by the Pigeonhole Principle, there are $C_{i}^{'}$ and $C_{j}^{'}$ ($3\leq i\neq j\leq 7$) adjacent to $x_{4}, x_{5}$ and the same $x_{r}$ in $\{ x_{1}, x_{2}, x_{3}\}$, and there is a $C_{k}^{'}$ ($k\neq i, j$ and $3\leq k\leq 7$) such that $C_{k}^{'}$ is adjacent to $x_{4}, x_{5}$. We use $C_{i}^{'}$ and $C_{j}^{'}$ to replace $C_{1}^{'}$ and $C_{2}^{'}$, and $C_{k}^{'}$ to replace $C_{3}^{'}$, then Case 1 still happens. The proof is the same as before.

Now suppose that Case 1 does not happen. Then, for any two vertices $C_{i}^{'}$ and $C_{j}^{'}$ ($1\leq i < j\leq 7$), $|N(C_{i}^{'})\cap N(C_{j}^{'}) | \leq 2$.

Case 2. Suppose there are two vertices $C_{i}^{'}$ and $C_{j}^{'}$ ($1\leq i < j\leq 7$) such that $|N(C_{i}^{'})\cap N(C_{j}^{'})| = 2$.

Without loss of generality, assume that $N(C_{1}^{'}) = \{ x_{1}, x_{2}, x_{3}\}$, $N(C_{2}^{'}) = \{ x_{2}, x_{3}, x_{4}\}$ such that $|N(C_{1}^{'})\cap N(C_{2}^{'})| = 2$.

Case (2.1). $C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}$ are adjacent to only vertices in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$.

Since $G$ is 3-connected and Case 1 does not happen, then $N(C_{3}^{'}) = \{ x_{1}, x_{2}, x_{4}\}$ and $N(C_{4}^{'}) = \{ x_{1}, x_{3}, x_{4}\}$. In $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}\}\cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}\}]$, any two of $x_{1}, x_{2}, x_{3}, x_{4}$ are symmetric, and any two of $C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}$ are symmetric. Since Case 1 does not happen, $N(C_{j}^{'})$ is not contained in $\{x_{1}, x_{2}, x_{3}, x_{4}\}$ ($j = 5, 6, 7$). So $C_{j}^{'}$ must be adjacent to $x_{5}$ ($j = 5, 6, 7$). By the symmetry of any two of $x_{1}, x_{2}, x_{3}, x_{4}$, we can assume that $C_{5}^{'}$ is adjacent to $x_{3}, x_{4}$. Also by the assumption of Case 2, $C_{6}^{'}$ is adjacent to $x_{1}$ and $x_{2}$, or adjacent to $x_{2}$ and $x_{3}$. In the first case, $\{ x_{1}, x_{2}\}$ and $\{ x_{3}, x_{4}\}$ are symmetric, then $C_{1}^{'}$ is adjacent to $x_{1}, x_{2}, x_{3}$, $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}$, and $C_{2}^{'}$ is connected to $x_{1}$ by path $C_{2}^{'}x_{4}C_{3}^{'}x_{1}$, $C_{6}^{'}$ is adjacent to $x_{1}, x_{2}$, and $C_{6}^{'}$ is connected to $x_{3}$ by path $C_{6}^{'}x_{5}C_{5}^{'}x_{3}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction. In the second case, $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}, x_{4}$, $C_{4}^{'}$ is adjacent to $x_{3}, x_{4}$, and is connected to $x_{2}$ by path $C_{4}^{'}x_{1}C_{1}^{'}x_{2}$, $C_{5}^{'}$ is adjacent to $x_{3}, x_{4}$, and is connected to $x_{2}$ by path $C_{5}^{'}x_{5}C_{6}^{'}x_{2}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{4}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

Case (2.2). $N(C_{i}^{'}) \subseteq \{ x_{1}, x_{2}, x_{3}, x_{4}\}$ for $i = 1, 2, 3$ but $N(C_{j}^{'}) \not\subseteq \{ x_{1}, x_{2}, x_{3}, x_{4} \}$ for $4 \leq j \leq 7$.

Then $N(C_{3}^{'}) = \{ x_{1}, x_{2}, x_{4}\}$. (The case that $N(C_{3}^{'}) = \{ x_{1}, x_{3}, x_{4}\}$ is symmetric, and the proof is similar). As the neighbourhood of $C_{i}^{'}$ ($i = 4, 5, 6, 7$) is not contained in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$, $C_{i}^{'}$ is adjacent to $x_{5}$ for $i = 4, 5, 6, 7$. In $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}\}]$, any two of $x_{1}, x_{3}, x_{4}$ are symmetric, and any two of $C_{1}^{'}, C_{2}^{'}, C_{3}^{'}$ are symmetric. By the assumption of Case 2, we have the following four cases.

Case (2.2.1). Suppose $N(C_{4}^{'}) = \{ x_{3}, x_{4}, x_{5}\}$, $N(C_{5}^{'}) = \{ x_{1}, x_{4}, x_{5}\}$, and $N(C_{6}^{'}) = \{ x_{1}, x_{3}, x_{5}\}$.

Notice that any two of $x_{1}, x_{3}, x_{4}$ are symmetric, since Case (2.1) does not happen, $N(C_{7}^{'})$ is not contained in $\{ x_{1}, x_{3}, x_{4}, x_{5}\}$, without loss of generality, assume that $N(C_{7}^{'}) = \{ x_{2}, x_{3}, x_{5}\}$. Now $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}, x_{4}$, $C_{1}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{4}$ by path $C_{1}^{'}x_{1}C_{3}^{'}x_{4}$, $C_{7}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{4}$ by path $C_{7}^{'}x_{5}C_{4}^{'}x_{4}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

Case (2.2.2). Suppose $N(C_{4}^{'}) = \{ x_{3}, x_{4}, x_{5}\}$, $N(C_{5}^{'}) = \{ x_{1}, x_{3}, x_{5}\}$.

Now $x_{1}$ and $x_{4}$ are symmetric. By the assumption of Case 2, as Case (2.2.1) does not hold, we have two cases: $N(C_{6}^{'}) = \{ x_{2}, x_{4}, x_{5}\}$; or $N(C_{6}^{'}) = \{x_{2}, x_{3}, x_{5}\}$. Suppose $N(C_{6}^{'}) = \{ x_{2}, x_{4}, x_{5}\}$. Then $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}, x_{4}$, $C_{1}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{4}$ by path $C_{1}^{'}x_{1}C_{3}^{'}x_{4}$, $C_{6}^{'}$ is adjacent to $x_{2}, x_{4}$, and is connected to $x_{3}$ by path $C_{6}^{'}x_{5}C_{5}^{'}x_{3}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, \; x_{5} \} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, contradicting to the fact that $G'$ is planar. Suppose $N(C_{6}^{'}) = \{ x_{2}, x_{3}, x_{5}\}$. Then $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}, x_{4}$, $C_{1}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{4}$ by path $C_{1}^{'}x_{1} \; C_{3}^{'}x_{4}$, $C_{6}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{4}$ by path $C_{6}^{'}x_{5}C_{4}^{'}x_{4}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

Case (2.2.3). Suppose $N(C_{4}^{'}) = \{ x_{3}, x_{4}, x_{5}\}$.

Now $x_{3}$ and $x_{4}$ are symmetric. We have two cases: (1) $N(C_{5}^{'}) = \{ x_{2}, x_{3}, x_{5}\}$, $N(C_{6}^{'}) = \{x_{2}, x_{4}, x_{5}\}$; (2) $N(C_{5}^{'}) = \{ x_{2}, x_{3}, x_{5}\}$, $N(C_{6}^{'}) = \{ x_{1}, x_{2}, x_{5}\}$.

In the first case, $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}, x_{4}$, $C_{1}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{4}$ by path $C_{1}^{'}x_{1}C_{3}^{'}x_{4}$, $C_{6}^{'}$ is adjacent to $x_{2}, x_{4}$, and is connected to $x_{3}$ by path $C_{6}^{'}x_{5}C_{5}^{'}x_{3}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{5}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

In the second case, $C_{1}^{'}$ is adjacent to $x_{1}, x_{2}, x_{3}$, $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{1}$ by path $C_{2}^{'}x_{4}C_{3}^{'}x_{1}$, $C_{6}^{'}$ is adjacent to $x_{1}, x_{2}$, and is connected to $x_{3}$ by path $C_{6}^{'}x_{5}C_{4}^{'}x_{3}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

There remains the last case in Case (2.2) as follows.

Case (2.2.4). Suppose $N(C_{4}^{'}) = \{ x_{2}, x_{3}, x_{5}\}$, $N(C_{5}^{'}) = \{x_{2}, x_{4}, x_{5}\}$, $N(C_{6}^{'}) = \{ x_{1}, x_{2}, x_{5}\}$.

Now $C_{1}^{'}$ is adjacent to $x_{1}, x_{2}, x_{3}$, $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{1}$ by path $C_{2}^{'}x_{4}C_{3}^{'}x_{1}$, $C_{6}^{'}$ is adjacent to $x_{1}, x_{2}$, and is connected to $x_{3}$ by path $C_{6}^{'}x_{5}C_{4}^{'}x_{3}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{6}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

Case (2.3). Suppose only $C_{1}^{'}, C_{2}^{'}$ are adjacent only to vertices in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$.

Since $N(C_{i}^{'}$) is not contained in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$, $C_{i}^{'}$ is adjacent to $x_{5}$ for $i = 3, 4, \cdots, 7$. Now $x_{1}$ and $x_{4}$ are symmetric, $x_{2}$ and $x_{3}$ are symmetric in $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}\} \cup \{ C_{1}^{'}, C_{2}^{'}\}]$. By the assumption of Case 2, each $C_{i}^{'}$ is adjacent to exactly two vertices in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$ besides $x_{5}$ ($i = 3, 4, \cdots, 7$), and $C_{i}^{'}$ and $C_{j}^{'}$ ($3\leq i < j\leq 7$) are not adjacent to the same two vertices in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$. Since the number of combinations of two vertices in $\{x_{1}, x_{2}, x_{3}, x_{4}\}$ is totally $C(4, 2) = \frac{4\times 3}{2!} = 6$, there is exactly one combination of two vertices which are not adjacent to the same $C_{i}^{'}$ ($3\leq i\leq 7$), and for each of the other combinations of two vertices in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$, the two vertices are both adjacent to one $C_{i}^{'}$ ($3\leq i\leq 7$). Considering the symmetry of the roles of $C_{i}^{'}$ ($i = 3, 4, \cdots, 7$), there are six cases to take five combinations from the totally six combinations of two vertices in $\{ x_{1}, x_{2}, x_{3}, x_{4}\}$ such that the two vertices of each of the five combinations are both adjacent to a $C_{i}^{'}$ ($3\leq i\leq 7$). Also considering the symmetry of $x_{1}$ and $x_{4}$, and $x_{2}$ and $x_{3}$, there remains 3 cases as follows.

Case (2.3.1). No $C_{i}^{'}$ ($3\leq i\leq 7$) is adjacent to both $x_{1}$ and $x_{4}$.

Since the roles of $C_{3}^{'}, C_{4}^{'}, \cdots, C_{7}^{'}$ are symmetric, without loss of generality, assume that $N(C_{3}^{'}) = \{ x_{1}, x_{2}, x_{5}\}$, $N(C_{4}^{'}) = \{ x_{3}, x_{4}, x_{5}\}$, $N(C_{5}^{'}) = \{x_{2}, x_{4}, x_{5}\}$, $N(C_{6}^{'}) = \{ x_{1}, x_{3}, x_{5}\}$, $N(C_{7}^{'}) = \{ x_{2}, x_{3}, x_{5}\}$.

Now $C_{7}^{'}$ is adjacent to $x_{2}, x_{3}, x_{5}$, $C_{4}^{'}$ is adjacent to $x_{3}, x_{5}$, and is connected to $x_{2}$ by path $C_{4}^{'}x_{4}C_{2}^{'}x_{2}$, $C_{3}^{'}$ is adjacent to $x_{2}, x_{5}$, and is connected to $x_{3}$ by path $C_{3}^{'}x_{1}C_{6}^{'}x_{3}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{6}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

Case (2.3.2). No $C_{i}^{'}$ ($3\leq i\leq 7$) is adjacent to both $x_{1}$ and $x_{2}$. (For $x_{1}, x_{3}$; $x_{2}, x_{4}$; $x_{3}, x_{4}$, the discussion is similar.)

Since the roles of $C_{3}^{'}, C_{4}^{'}, \cdots, C_{7}^{'}$ are symmetric, without loss of generality, assume that $N(C_{3}^{'}) = \{ x_{1}, x_{4}, x_{5}\}$, $N(C_{4}^{'}) = \{ x_{1}, x_{3}, x_{5}\}$, $N(C_{5}^{'}) = \{ x_{2}, x_{4}, x_{5}\}$, $N(C_{6}^{'}) = \{ x_{3}, x_{4}, x_{5}\}$, $N(C_{7}^{'}) = \{x_{2}, x_{3}, x_{5}\}$.

Now $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}, x_{4}$, $C_{1}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{4}$ by path $C_{1}^{'}x_{1}C_{3}^{'}x_{4}$, $C_{5}^{'}$ is adjacent to $x_{2}, x_{4}$, and is connected to $x_{3}$ by path $C_{5}^{'}x_{5}C_{7}^{'}x_{3}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{5}^{'}, C_{7}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

Case (2.3.3). No $C_{i}^{'}$ ($3\leq i\leq 7$) is adjacent to both $x_{2}$ and $x_{3}$.

Since the roles of $C_{3}^{'}, C_{4}^{'}, \cdots, C_{7}^{'}$ are symmetric, without loss of generality, assume that $N(C_{3}^{'}) = \{ x_{1}, x_{4}, x_{5}\}$, $N(C_{4}^{'}) = \{ x_{1}, x_{2}, x_{5}\}$, $N(C_{5}^{'}) = \{ x_{1}, x_{3}, x_{5}\}$, $N(C_{6}^{'}) = \{ x_{2}, x_{4}, x_{5}\}$, $N(C_{7}^{'}) = \{ x_{3}, x_{4}, x_{5}\}$.

Now $C_{1}^{'}$ is adjacent to $x_{1}, x_{2}, x_{3}$, $C_{2}^{'}$ is adjacent to $x_{2}, x_{3}$, and is connected to $x_{1}$ by path $C_{2}^{'}x_{4}C_{3}^{'}x_{1}$, $C_{4}^{'}$ is adjacent to $x_{1}, x_{2}$, and is connected to $x_{3}$ by path $C_{4}^{'}x_{5}C_{5}^{'}x_{3}$. So $G'[\{ x_{1}, x_{2}, x_{3}, x_{4}, x_{5}\} \cup \{ C_{1}^{'}, C_{2}^{'}, C_{3}^{'}, C_{4}^{'}, C_{5}^{'}\}]$ contains a subdivision of $K_{3, 3}$, a contradiction.

Case 3. Suppose that, for any two vertices $C_{i}^{'}$ and $C_{j}^{'}$ ($1\leq i < j\leq 7$), $|N(C_{i}^{'})\cap N(C_{j}^{'})|\leq 1$ and Cases 1 and 2 do not hold.

Since $|N(C_{i}^{'})| = |N(C_{j}^{'})| = 3$ and $|S| = 5$, $|N(C_{i}^{'})\cap N(C_{j}^{'})| = 1$ ($1\leq i < j\leq 7$). Without loss of generality, assume that $N(C_{1}^{'}) = \{ x_{1}, x_{2}, x_{3}\}$, and $N(C_{2}^{'}) = \{ x_{3}, x_{4}, x_{5}\}$. Then $N(C_{1}^{'})\cap N(C_{2}^{'}) = \{ x_{3}\}$. By the assumption of Case 3, $|N(C_{3}^{'})\cap N(C_{1}^{'})| = 1$, then there are two vertices of $N(C_{3}^{'})$ which are not in $\{ x_{1}, x_{2}, x_{3}\}$, hence $|N(C_{3}^{'})\cap N(C_{2}^{'})|\geq 2$, which contradicts the assumption of Case 3.

In all cases discussed above, we can always obtain contradiction. So $\omega (G-S)\geq |S|+2$ does not hold. By Lemma 1, when $\nu (G)\geq 2k$, $G$ is k-subconnected for $k = 4, 5, 6$.

Remark 1. Now we give some counterexamples to show the sharpness of Corollaries 7 and 8, and Theorem 10. Let $H$ be a connected planar graph, let $G_{1}, G_{2}, G_{3}$ be three copies of $H$, and let $v$ be a vertex not in $G_{i}$ ($i = 1, 2, 3$). Let $G$ be the graph such that $v$ is joined to $G_{i}$ ($i = 1, 2, 3$) by an edge respectively. Then $G$ is a 1-connected planar graph, but $G$ is not 2-subconnected since we take a vertex $v_{i}$ in $G_{i}$ ($i = 1, 2, 3$) and let $v_{4} = v$, then there are not two independent paths joining $v_{1}, v_{2}, v_{3}, v_{4}$ in two pairs in $G$. So Corollary 7 is sharp.

Let $H$ be a planar embedding of a 2-connected planar graph, let $G_{1}, G_{2}, G_{3}, \; G_{4}$ be four copies of $H$, let $v_{5}$ and $v_{6}$ be two vertices not in $G_{i}$ ($i = 1, 2, \; 3, 4$). Let $G$ be the graph such that $v_{5}$ and $v_{6}$ are joined to two different vertices on the outer face of $G_{i}$ ($i = 1, 2, 3, 4$) by edges respectively. Then $G$ is a 2-connected planar graph, but is not 3-subconnected since we take a vertex $v_{i}$ in $G_{i}$ ($i = 1, 2, 3, 4$), then there are not three independent paths joining $v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}$ in three pairs. So Corollary 8 is sharp.

Let $G_{0}$ be a triangle with vertex set $\{ v_{4}, v_{5}, v_{6}\}$, then insert a vertex $v_{i}$ into a triangle inner face of $G_{i-1}$ and join $v_{i}$ to every vertex on the face by an edge respectively to obtain $G_{i}$ for $i = 1, 2, 3$. Let $G = G_{3}$. Notice that $\nu (G) = 6$, $\varepsilon (G_{0}) = 3$, and each time when we insert a vertex, the number of edges increases by 3. So $\varepsilon (G) = 3 + 3 + 3 + 3 = 12$. By the Euler's Formula, $\phi = \varepsilon - \nu + 2 = 12 - 6 + 2 = 8$. Let $H$ be a planar embedding of a 3-connected planar graph. Then put a copy of $H$ into every face of $G$ and join each vertex on the triangle face of $G$ to a distinct vertex on the outer face of $H$ to obtain a planar graph $G'$. Then $G'$ is a 3-connected planar graph with $\nu (G')\geq 2k$ for $k = 7$, but $G'$ is not 7-subconnected since we have a cutset $S = \{ v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{6}\}$, but $G^{'}-S$ has 8 copies of $H$ (8 components) and $\omega (G^{'}-S) = 8\geq |S| + 2$. By Lemma 1, the conclusion holds. So Theorem 10 is sharp.

Remark 2. For a 3-connected planar graph $G$ with at least $2k$ vertices, by Lemma 6, $G$ is obviously k-subconnected for $k = 1, 2, 3$.

4.   Conclusions

In the last section, we prove the k-subconnectivity of $k'$-connected planar graphs for $k' = 1, 2, \cdots, 5$.

Since a k-subconnected graph is a spanning substructure of a k-connected graph, in the future, we can work on the number of edges deleted from a k-connected graph such that the resulting graph is still k-subconnected.

We may also extend the k-subconnectivity of planar graphs to find the subconnectivity of general graphs with a higher genus.