# G is k-connected, then there is a cycle in G containing all $x_i$.

Let $$G$$ be a $$k$$-connected graph $$(k ≥ 2)$$, and let $$x_1,x_2,...,x_k$$ be vertices of $$G$$. Show that there is a cycle in $$G$$ containing all the $$x_i$$.

First, Assum that $$G$$ is $$k$$-connected graph $$(k ≥ 2)$$ on $$n$$ vertices.

So $$G-x_1-x_2...-x_k$$ is disconnected then we have only two components.

How i prove that there is a cycle in $$G$$ containing all the $$x_i$$ for all $$i$$.

One way to do this is by induction on $$k$$. To go from $$k-1$$ to $$k$$, suppose that $$C$$ is the cycle containing $$v_1, \dots, v_{k-1}$$ and $$v_k \notin C$$. We'll use Menger's theorem to make the desired cycle from $$C$$:
• If $$|C| \geq k$$, there are $$k$$ internally disjoint paths from $$v_k$$ to $$C$$, each ending on a different endpoint in $$C$$. At least two consecutive endpoints (say the endpoints of paths $$p_i$$ and $$p_j$$) do not have any of $$v_i$$ $$(1 \leq i \leq k-1)$$ on the path between them in $$C$$ (why?), and so one can replace it with $$p_i$$ and $$p_j$$ to get a cycle that contains all $$v_1, \dots, v_k$$.
• If $$|C| = k-1$$, there are $$k-1$$ internally disjoint paths from $$v_k$$ to $$C$$, each ending on a different $$v_i$$. Take any two adjacent endpoints, and replace the edge between them in $$C$$ with their paths to $$v_k$$.
It remains to prove for $$k=2$$. This case is well-known (actually a stronger version holds: $$2$$-connected $$\iff$$ every two vertices are in a cycle). That being said, we could still use Menger's theorem to say there are two internally disjoint paths from $$v_1$$ to $$v_2$$, the union of which makes a cycle.