1
$\begingroup$

I'm studying for a graph theory exam and am stumped on one of the practice questions:

Suppose $G$ is $2$-vertex-connected. Show that for any distinct vertices $x$, $y$, $z$ of $G$ there exists a path from $x$ to $y$ containing $z$.

I've tried working with ear decompositions and Menger's theorem (since those are the two major focuses we had in class about 2-connected graphs) but I keep ending up with a walk from $x$ to $y$ containing $z$, which isn't good enough because there's no guarantee that $z$ will exist in the resulting path.

1 Answers 1

3

Since $G$ is 2-connected, there must exist a cycle $C$ containing $y$ and $z$.

Now, we construct the path $P_{xzy}$ as follows:

Pick any path $P_{xz}$ from $x$ to $z$. If the only vertex it shares with $C$ is $z$ we're done because $P_{xzy}$ is constructed by first following $P_{xz}$ and then following along the cycle from $z$ to $y$.

Otherwise, follow $P_{xz}$ until we find a vertex shared by $P_{xz}$ and $C$, and then follow along $C$ to get $z$ and then $y$.

That is, we pick the shortest prefix $P_{xz}'$ = $x u_1 u_2 \cdots u_k$ of the path $P_{xz}$ such that the first shared vertex between $P_{xz}'$ and $C$ is $u_k$. Then the cycle $C$ is $u_k v_1 \cdots v_m z v_{m+1} \cdots v_j y v_{j+1} \cdots v_n u_k$ for some vertices $v_i \neq y$.

Hence we set $P_{xzy} = x u_1 u_2 \cdots u_k v_1 \cdots v_m z v_{m+1} \cdots v_j y$.