## Oriented Eulerian graphs

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.  