Eulerian and Hamiltonian Graphs: Two Classical Traversal Problems
From the Bridges of Königsberg to Euler's theorem on Eulerian circuits, directed Eulerian graphs, Hamiltonian cycles, the theorems of Ore and Dirac, and the NP-completeness of the Hamiltonian cycle problem.
1 The Bridges of Königsberg
In 1736, Euler investigated whether it was possible to walk through the city of Kö
Modeling the problem as a multigraph, vertex has degree and each of has degree . Since every vertex has odd degree, the theorem below implies that no Eulerian circuit exists.
2 Eulerian Circuits and Trails
Definition 1 (Eulerian circuit and Eulerian trail).
An Eulerian circuit of a graph is a closed trail that traverses every edge of exactly once. An Eulerian trail is a trail (not necessarily closed) that traverses every edge exactly once. A graph that possesses an Eulerian circuit is called an Eulerian graph.
Theorem 2 (Euler's theorem).
A connected graph has an Eulerian circuit if and only if every vertex of has even degree.
Proof.
Each time the Eulerian circuit passes through a vertex , it uses one edge to enter and one edge to leave, contributing to . Since every edge is used exactly once, is even. Assume every vertex has even degree. We proceed by induction on the number of edges . If , the result is trivial. Suppose .Since every vertex has degree at least , the graph contains a cycle (start at any vertex and follow unvisited edges; finiteness forces a return to a previously visited vertex). Consider . Because removes an even number of edges at each vertex, every vertex of still has even degree. By the induction hypothesis, each connected component of has an Eulerian circuit.We now splice these circuits together: traverse , and whenever passes through a vertex that belongs to a component of , detour along that component's Eulerian circuit before continuing along . Since is connected, every component of shares at least one vertex with , so the splicing covers all edges. □
Theorem 3 (Existence of an Eulerian trail).
A connected graph has an Eulerian trail if and only if the number of vertices of odd degree is exactly or . In the former case the trail is a circuit; in the latter, the trail runs between the two odd-degree vertices.
Proof.
When there are exactly two vertices of odd degree, say and , add the edge to obtain , in which every vertex has even degree. By Euler's theorem, has an Eulerian circuit. Deleting the added edge from this circuit yields an Eulerian trail from to . □
3 Directed Eulerian Graphs
Theorem 4 (Directed Euler's theorem).
A connected directed graph has an Eulerian circuit (a directed closed trail traversing every arc exactly once) if and only if (out-degree equals in-degree) for every vertex .
Proof.
The argument parallels the undirected case. Each passage through a vertex uses one incoming and one outgoing arc, making necessary. Sufficiency is established by extracting a directed cycle and inductively merging the circuits of the remaining components. □
4 Hamiltonian Cycles
Definition 5 (Hamiltonian cycle and Hamiltonian path).
A cycle that visits every vertex of exactly once is called a Hamiltonian cycle. A path that visits every vertex exactly once is a Hamiltonian path. A graph possessing a Hamiltonian cycle is called a Hamiltonian graph.
Remark 6.
An Eulerian circuit traverses every edge; a Hamiltonian cycle visits every vertex. The former can be decided in polynomial time, while the latter is dramatically harder.
Theorem 7 (Dirac's theorem (1952)).
If is a simple graph on vertices with for every vertex , then is Hamiltonian.
Proof.
Suppose, for contradiction, that is a non-Hamiltonian graph with minimum degree at least and the maximum possible number of edges. Since adding any edge to would create a Hamiltonian cycle, contains a Hamiltonian path .We have (otherwise would be Hamiltonian). Define the sets
Since and , and both and are subsets of , we have . By the pigeonhole principle, .Pick . Then and , so
is a Hamiltonian cycle, contradicting our assumption. □
Theorem 8 (Ore's theorem (1960)).
If is a simple graph on vertices such that for every pair of non-adjacent vertices , then is Hamiltonian.
Remark 9.
Dirac's theorem is a corollary of Ore's theorem: if , then for any non-adjacent pair we have .
5 NP-Completeness
Remark 10.
The Hamiltonian cycle problem — deciding whether a given graph contains a Hamiltonian cycle — is -complete. It is one of the problems shown to be -complete by Karp (1972). Assuming , no polynomial-time algorithm exists. By contrast, the existence of an Eulerian circuit can be decided in time simply by checking that every vertex has even degree. This stark difference in computational complexity highlights a fundamental distinction between traversing all edges and visiting all vertices.
FO
Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.
1 フォロワー·105 記事