Task list filter?

Choose required ranks and required tasks. The table of contents will list only tasks having one of the required ranks in corresponding rankings and at least one of the required tags (overall). If you wish to filter only according to some rankings or tags, leave the other groups empty.

Task rankings

Difficulty level

Task tags

Task type
«
«
«

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.

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