## Vertices on a common cycle

Prove the following statement: Let $$G$$ be a (vertex) 2-connnected graph and $$u$$, $$v$$ two of its vertices. Then there is a cycle in $$G$$ containing $$u$$ and $$v$$.

• #### Hint

Use an eared lemma or one of Menger’s theorems.

• #### Solution

The statement evidently holds for a cycle.

If $$U$$ is an ear and the statement holds for $$G-U$$, then it is necessary to distinguish the cases according to the position of $$u$$ and $$v$$ with respect to of $$U$$:

If $$u, v \notin U$$, then we find the cycle according to the inductive hypothesis.

If $$u, v \in U$$, then we find a cycle $$C$$ in $$G-U$$ containing the end vertices $$x, y$$ of the ear $$U$$. From this cycle, we choose one of the paths between $$x$$ and $$y$$ and complete it with $$U$$ for the wanted cycle.

If $$u \in U$$ and $$v \notin U$$, then first we find the cycle $$C$$ in $$G-U$$ passing $$x$$ and $$u$$ and also some path from $$y$$ to any $$C$$ vertex other than $$x$$. In this subgraph we can already find the cycle.

Menger’s theorem makes the argument easier: we merge the two vertex disjoint paths directly into a cycle.  