Eulerian & Hamiltonian Paths

1. Introduction

In graph theory, the study of paths and cycles that traverse graphs in specific ways forms one of the most elegant and practically important areas of discrete mathematics. Two concepts stand at the forefront of this study: Eulerian paths and Hamiltonian paths.

These concepts are named after two legendary mathematicians — Leonhard Euler (1707–1783), who solved the famous Seven Bridges of Königsberg problem in 1736, and Sir William Rowan Hamilton (1805–1865), who created a mathematical game involving visiting every vertex of a graph exactly once.

While both concepts deal with traversing graphs, they address fundamentally different questions. Eulerian paths concern traversing every edge exactly once, while Hamiltonian paths concern visiting every vertex exactly once. This seemingly small distinction leads to dramatically different mathematical properties and computational complexity.

2. Eulerian Paths

2.1 Definition

An Eulerian path concept originates from one of the earliest problems in graph theory. Let us formalize the definitions:

The crucial distinction: an Eulerian path does not need to return to its starting vertex, while an Eulerian circuit does. Every Eulerian circuit is an Eulerian path, but the converse is not true.

2.2 Eulerian Circuits

Before we state Euler's famous theorem, let us introduce the concept of vertex degree. The degree of a vertex v, denoted deg(v), is the number of edges incident to v. A vertex with odd degree is called an odd vertex; one with even degree is an even vertex.

2.3 Euler's Theorem

Leonhard Euler provided a complete characterization of when a connected graph admits an Eulerian path or circuit. This result, published in 1736, is widely considered the first paper in graph theory.

Proof sketch: For an Eulerian circuit, every time the path enters a vertex via one edge, it must leave via another edge. This pairs up edges incident to each vertex, meaning every vertex must have even degree. Conversely, if all degrees are even, the graph decomposes into edge-disjoint cycles, which can be stitched together to form an Eulerian circuit.

For the Eulerian path case (exactly two odd-degree vertices), the two odd-degree vertices serve as the unique start and end points. At all other vertices, the path enters and leaves in pairs.

2.4 Hierholzer's Algorithm

While Euler's theorem tells us whether an Eulerian circuit exists, Hierholzer's algorithm (1873) provides an efficient method to actually construct one.

Algorithm overview:

1. Start at any vertex and follow unused edges, forming a cycle, until returning to the start vertex.
2. If there are unused edges remaining, find a vertex on the current cycle that has unused incident edges.
3. Starting from that vertex, trace another cycle through unused edges.
4. S splice this new cycle into the existing tour.
5. Repeat until all edges are used.

def hierholzer(graph):
    """Find an Eulerian circuit using Hierholzer's algorithm.""
    adj = {v: list(edges) for v, edges in graph.items()}
    circuit = []

    def dfs(vertex):
        while adj[vertex]:
            next_v = adj[vertex].pop()
            adj[next_v].remove(vertex)
            dfs(next_v)
        circuit.append(vertex)

    start = next(iter(graph))
    dfs(start)
    return circuit[::-1]

# Time Complexity: O(E) where E is the number of edges

The algorithm runs in O(E) time, where E is the number of edges, making it optimally efficient for this problem.

3. Hamiltonian Paths

3.1 Definition

Unlike Eulerian paths, which focus on edges, Hamiltonian paths focus on vertices. This shift in focus makes the problem dramatically harder from a computational perspective.

3.2 Hamiltonian Cycles

The most famous Hamiltonian problem is determining whether a given graph contains a Hamiltonian cycle. This problem was popularized by Hamilton's Icosian Game (1859), which involved finding a Hamiltonian cycle on the edges of a dodecahedron.

3.3 Sufficient Conditions

While no simple necessary and sufficient condition exists for Hamiltonian cycles (as would be required for a polynomial-time characterization), several sufficient conditions have been established.

Note that Ore's theorem generalizes Dirac's theorem: if every vertex has degree at least n/2, then for any pair of non-adjacent vertices, their degree sum is at least n. Both conditions are sufficient but not necessary — many Hamiltonian graphs do not satisfy either condition.

4. Key Differences

The table below summarizes the fundamental differences between Eulerian and Hamiltonian paths:

5. Algorithms

5.1 Finding Eulerian Paths

Finding an Eulerian path or circuit is straightforward thanks to the efficient algorithms available:

• Hierholzer's Algorithm — O(E) time, as described above
• Fleury's Algorithm — O(E²) time, simpler to implement but less efficient. It avoids bridges (edges whose removal disconnects the graph) unless no alternative exists.

5.2 Finding Hamiltonian Paths

Due to the NP-completeness of the Hamiltonian path problem, no efficient general algorithm exists. Common approaches include:

• Backtracking — systematic search with pruning. Exponential in the worst case.
• Dynamic Programming — the Held-Karp algorithm runs in O(n² · 2ⁿ) time, which is still exponential but faster than brute force O(n!).
• Heuristics — nearest-neighbor, randomized local search, genetic algorithms.
• Integer Linear Programming — formulate as an ILP and use solvers like CPLEX or Gurobi.

def hamiltonian_path(graph, n):
    """Find a Hamiltonian path using backtracking.""
    path = [-1] * n
    path[0] = 0  # Start from vertex 0
    visited = [False] * n
    visited[0] = True

    def util(v, pos):
        if pos == n:
            return True
        for i in graph[v]:
            if not visited[i]:
                visited[i] = True
                path[pos] = i
                if util(i, pos + 1):
                    return True
                visited[i] = False
                path[pos] = -1
        return False

    if util(0, 1):
        return path
    return None

# Worst-case: O(n!) time complexity

6. Applications

6.1 Eulerian Paths in Practice

• Route optimization — postal delivery routes, street sweeping, snow plowing (the "Chinese Postman Problem" is a generalization)
• Circuit design — testing printed circuit boards, where every wire (edge) must be tested
• Bioinformatics — DNA sequence assembly using De Bruijn graphs, where reads are edges and k-mers are vertices
• Network monitoring — ensuring every communication link is inspected
• Language processing — palindrome construction and string problems

6.2 Hamiltonian Paths in Practice

• Traveling Salesman Problem (TSP) — the Hamiltonian cycle problem is a special case of TSP where all edge weights are equal
• Logistics — visiting every location exactly once in delivery routes
• VLSI design — testing integrated circuits, pin assignment problems
• Genetics — genome rearrangement problems
• Scheduling — arranging tasks so each is performed exactly once with minimum transitions

7. Famous Problems

7.1 The Seven Bridges of Königsberg (1736)

The city of Königsberg (now Kaliningrad, Russia) was built around the Pregel River, with two islands connected to each other and the mainland by seven bridges. The question was: Can one walk through the city crossing each bridge exactly once?

Euler proved it was impossible. Modeling the land masses as vertices and bridges as edges, he showed that all four vertices had odd degree. By his theorem, a graph needs at most two odd-degree vertices to have an Eulerian path. Since Königsberg had four, no such walk exists.

7.2 The Icosian Game (1859)

Hamilton created a mathematical puzzle using a dodecahedron (a solid with 20 vertices and 30 edges). The goal was to find a Hamiltonian cycle — a path that visits each of the 20 vertices exactly once and returns to the start. The game was marketed as the "Around the World" puzzle.

7.3 The Traveling Salesman Problem

The TSP asks: given a set of cities and distances between them, find the shortest possible route that visits each city exactly once and returns to the origin. When all distances are equal, this reduces to finding a Hamiltonian cycle — making TSP a weighted generalization of the Hamiltonian cycle problem.

8. Conclusion

Eulerian and Hamiltonian paths represent two of the most fundamental and beautifully contrasting concepts in graph theory. Eulerian paths, with their elegant necessary-and-sufficient conditions and efficient algorithms, exemplify problems that mathematics can completely solve. Hamiltonian paths, with their computational intractability, stand as a monument to the limits of algorithmic computation.

Together, they illustrate a profound truth: changing a problem's focus from edges to vertices can transform it from trivial to intractable. This tension between structure and complexity continues to drive research in combinatorics, computer science, and operations research.

Whether you're assembling a genome, planning a delivery route, or simply tracing a path through a network, the insights of Euler and Hamilton remain as relevant today as they were centuries ago.