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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email