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:
- All vertices in G have even degree.
- G consists of the edges from a disjoint union of some cycles, and the vertices from these cycles.
- 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.
Read more about this topic: Route Inspection Problem
Famous quotes containing the words paths and/or circuits:
“Now it is the time of night
That the graves, all gaping wide,
Every one lets forth his sprite
In the church-way paths to glide.”
—William Shakespeare (1564–1616)
“The Buddha, the Godhead, resides quite as comfortably in the circuits of a digital computer or the gears of a cycle transmission as he does at the top of a mountain or in the petals of a flower.”
—Robert M. Pirsig (b. 1928)