An Eulerian circuit is a trail that starts and ends at the same graph vertex and uses each graph edge exactly once. 1
More formally,
Definition
Let
be a connected graph, an Eulerian circuit in is a walk . which
- uses every edge exactly once, i.e. for every
, there is exactly one such that - returns to its starting point, i.e.
A connected graph
is said to be Eulerian if it has an Eulerian circuit.
If an Eulerian circuit does exist, you can make it start (and therefore finish) at any vertex.
Example
Consider the following 2 graphs,
The first one is Eulerian, with an example walk
. The second one is not Eulerian.
Euler observed that whether an Eulerian circuit exists depends on vertex degree. Every time a circuit visits a vertex, it must arrive on one degree and leave on another:
Theorem
A connected graph
is Eulerian if and only if is even for every vertex in .
There is an easy variant of the above Theorem for the case of an Eulerian trail, which uses every edge exactly once but finishes at a different vertex.
Theorem
A connected graph
has an Eulerian trail if and only if it has exactly two vertices of odd degree. If this the case, the trail must start at one of these vertices of odd degree and finish at the other.
See Also
- Hamiltonian graph: need to visit every vertex once rather than to visit every edge once