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:
“The surface of the earth is soft and impressible by the feet of men; and so with the paths which the mind travels. How worn and dusty, then, must be the highways of the world, how deep the ruts of tradition and conformity!”
—Henry David Thoreau (1817–1862)
“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)