Vertices on a common cycle
Task number: 3967
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
By induction on adding ears.
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 through \( x \) and \(v\), 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.
