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 \).)
Solution
We will conduct the proof by contradiction. Let \( G \) be the smallest counterexample. Let us 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 connected, \( V_T \cap V_{T’} \ne\emptyset \), so the trail \( T’ \) could be insetred in the trail \( T \), which is a contradiction.
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
Consider the previous proof and observe that for \(V_T\cap V_{T'}\ne\emptyset\), it is sufficient for \(G\) to be only weakly connected.
We see that the equality of the input and output degrees actually strengthens the weak connectivity to strong.
