Route Inspection Problem - Eulerian Paths and Circuits

Eulerian Paths and Circuits

In order for a graph to have an Eulerian circuit, it will certainly have to be connected.

Suppose we have a connected graph G = (V, E), The following statements are equivalent:

1. All vertices in G have even degree.
2. G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
3. G has an Eulerian circuit.

• 1 → 2 can be shown by induction on the number of cycles.
• 2 → 3 can also be shown by induction on the number of cycles, and
• 3 → 1 should be immediate.

An Eulerian path (a walk which is not closed but uses all edges of G just once) exists if and only if G is connected and exactly two vertices have odd valence.