Prove that $G$ is $k$ connected iff for each 2-vertex $T \subset S$, there is a cycle of $G$ that contain both vertices in $T$

Question

Prove that $G$ of order $n \geq k+1 \geq 3$ is $k$ connected if and only if for each set $S$ of $k$ distinct vertices of $G$ and for each 2-vertex susbet $T$ of $S$, there is a cycle of $G$ that contain both vertices in $T$ but no vertices in $S-T$.

this I what I got so far

Let $G$ be a graph of order $n \geq k+1 \geq 3$, $S$ is the vertex cut of $G$, and $T \subset S$ such that $|T|=2$.

=>

Assume that $G$ is $k$ connected graph. Since $k+1 \geq 3$, $k \geq 2$, so every $k$ vertices of $G$ lies on a common cycle of $G$. I also know that for $u,v_1,v_2, \dots , v_t$ are $t+1$ distinct vertices in $G$ for $2 \leq t \leq k$, $G$ contain a $u-v_i$ path for each $1 \leq i \leq t$, every two paths of which have only $u$ in common.I also know that because $G$ is $k$ connected , for every pair $x,y$ of distinct vertices in $G$, $G$ has at least $k$ internal disjoint $x-y$ paths.

However I still can't see, how these information can help me get to the cycle that contain both vertices of $T$ but no vertex of $S-T$

Answer 1

=> We are told $G$ is $k$ connected. Let $T = \{u,v\}$. Then there are $k$ vertex disjoint $u$-$v$ paths in $G$. Union of any two of these $k$ paths will form a cycle containing both $u$ and $v$. So if you can show at least two of these $k$ paths do not contain anything from $S-T$, you are done. But this is easy because $|S-T| = k-2$, and so at most $k-2$ of these paths can have a vertex in $S-T$.

<= Suppose $T = \{u,v\}$. We are told for every $k$-vertex set $S$ containing $T$, there is a cycle in $G$ containing $u$ and $v$ but nothing in $S - T$. Suppose for a contradiction that such a $G$ is not $k$ connected.

That means there exists two vertices $u,v$ in $G$ with no more than $i$ vertex disjoint paths between them, where $2 \le i \le k-1$. Take $T = \{u,v\}$. At least $i-1$ of these vertex disjoint $u$-$v$ paths will each contain some internal vertex other than $u$ and $v$. Collect one internal vertex from each of these, say $w_1, \dots, w_{i-1}$. Take $S = T \cup \{w_1,\dots,w_{i-1}\}$. Clearly, $|S| \le k$, and so there is a cycle in $G$ containing $u$ and $v$ but none of the $w_i$s. But such a cycle will give two vertex disjoint $u$-$v$ paths that are distinct from the $i-1$ paths that gave the $w_i$s. Thus there are $i+1$ vertex disjoint $u$-$v$ paths in $G$, which is a contradiction!

Answer 2

If the graph $G$ is $k$-connected, deleting $k-2$ vertices will leave it $2$-connected. Thus the graph $H=G-(S-T)$ is $2$-connected. Let $T=\{u,v\}$. Since $u,v$ are two vertices of the $2$-connected graph $H$, they lie on a cycle of $H$. Of course that cycle does not contain any vertices from $S-T$, because those vertices have been deleted.

Conversely, suppose $G$ has the property "for each set $S$ of $k$ distinct vertices of $G$ and for each 2-vertex subset $T$ of $S$, there is a cycle of $G$ that contain both vertices in $T$ but no vertices in $S-T$." In other words, if we delete any $k-2$ vertices of $G$, the remaining graph will have the property that any two vertices lie on a cycle; thus, we have to delete at least two more vertices to get a disconnected graph; so $G$ is $k$-connected.