2
$\begingroup$

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$.

Maybe suppose that contradict?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.