Oriented Eulerian graphs

Task number: 4180

Prove that an oriented graph \( G \) has a closed Eulerian trail if and only if \( G \) is strongly connected and the indegree of each vertex is equal to its outdegree.

(Strong connectivity means that between each pair of vertices \( u \) and \( v \) there is an oriented path from \( u \) to \( v \), such an oriented path from \( v \) to \( u \).)

  • Variant

    Prove a stronger variant of this statement, where the strong connectivity is replaced by weak connectivity.

    (Weak connectivity means that between any two vertices there is a path whose edges can be oriented both along or against the direction of the path.)

  • Solution

    We will conduct the proof by contradiction, similarly to the non-oriented case.

    Let \( G \) be the smallest counterexample. Let’ choose the longest closed oriented trail \( T \) in \( G \). By removing \( T \) from \( G \), it remains valid that the input and output degrees are the same for each vertex in the remaining graph.

    If \( T \) does not contain all edges, then \( G-T \) has a non-empty component. From the induction hypothesis, this component can be covered by a closed oriented Eulerian trail \( T’ \).

    Because \( G \) is (strongly/weakly) connected, \( V_T \cap V_{T’} \ne\emptyset \), so the trail \( T’ \) could be insetred in the trail \( T \), which is a contradiction.

    We see that the equality of the input and output degrees actually strengthens the weak connectivity to strong.

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