Task list filter?
Task rankings
Task tags
«
«
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, VT∩VT′≠∅, 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 VT∩VT′≠∅, 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.