Eulerian vs. Hamiltonian: Paths and Cycles

The Königsberg Bridge Problem and Eulerian Paths

In the 18th century, the city of Königsberg (now Kaliningrad) was set on a river and included two large islands connected to each other and the mainland by seven bridges. A popular puzzle of the time was to find a walk through the city that would cross each of the seven bridges exactly once.

The great mathematician Leonhard Euler solved this by modeling the problem with a graph. He represented the land masses as vertices and the bridges as edges. This transformed the puzzle into a question about the graph: can you trace a path that covers every edge exactly once?

This leads us to the formal definitions of Eulerian paths and circuits.

As the video explains, the key to identifying Eulerian paths lies entirely in the degrees of the vertices. Let's formalize Euler's findings for a connected, undirected graph:

• An Eulerian Circuit is a path that traverses every edge exactly once and starts and ends at the same vertex. A graph has an Eulerian circuit if and only if every vertex has an even degree.

  • Intuition: To complete a circuit, for any intermediate vertex you visit, you must enter it via one edge and leave it via another. This pairs up the edges connected to that vertex. The start/end vertex also follows this, as the final edge of the circuit pairs with the first edge.

• An Eulerian Path is a path that traverses every edge exactly once but starts and ends at different vertices. A graph has an Eulerian path if and only if it has exactly two vertices of odd degree. The path must start at one of the odd-degree vertices and end at the other.

  • Intuition: The two odd-degree vertices serve as the unique start and end points of the path. Every other vertex must have an even degree, as you must enter and leave it an equal number of times.

• If a graph has more than two vertices of odd degree, it has neither an Eulerian path nor a circuit. In the case of the Königsberg bridge problem, all four land masses (vertices) had an odd number of bridges (degree 3, 3, 3, and 5), so Euler proved such a walk was impossible.

For your GATE preparation, questions about Eulerian paths are often a quick check of vertex degrees. Given a graph, you can rapidly sum up the degrees to answer the question.

The Elusive Hamiltonian Path

Now, let's switch our focus from edges to vertices.

A Hamiltonian path is a path in a graph that visits every vertex exactly once. A Hamiltonian cycle (or circuit) is a Hamiltonian path where an edge connects the end vertex back to the start vertex, forming a cycle.

You might expect a similarly elegant rule for Hamiltonian cycles, but here lies one of the most significant distinctions in graph theory and computer science.

The problem of determining whether a graph has a Hamiltonian cycle is NP-complete. This means there is no known efficient (polynomial-time) algorithm to solve it for all graphs. You won't be asked to find a complex Hamiltonian cycle in the GATE exam. Instead, you'll be tested on certain sufficient conditions that guarantee a cycle exists.

Two of the most famous sufficient conditions are Dirac's Theorem and Ore's Theorem.

Let's summarize these crucial theorems for a simple graph G with n vertices, where n >= 3.

1. Dirac's Theorem (1952): If the degree of every vertex v is at least $n/2$, i.e., $\mathrm{deg}(v)\ge n/2$ for all $v\in V$, then G has a Hamiltonian cycle.

2. Ore's Theorem (1960): If for every pair of non-adjacent vertices u and v, the sum of their degrees is at least n, i.e., $\mathrm{deg}(u)+\mathrm{deg}(v)\ge n$, then G has a Hamiltonian cycle.

Crucial Point: These are sufficient, not necessary, conditions.

• If a graph satisfies Dirac's or Ore's theorem, it must have a Hamiltonian cycle.
• If a graph does not satisfy these theorems, it might still have a Hamiltonian cycle. The theorems give you no information in this case.

For example, a simple cycle graph $C_n$ on n vertices has a Hamiltonian cycle (it is one itself). However, every vertex has a degree of 2. If $n>4$, then $n/2>2$, so the graph does not satisfy Dirac's theorem, yet it clearly has a Hamiltonian cycle.

Eulerian vs. Hamiltonian: A Summary for GATE

This table summarizes the key differences, which are essential to remember.

Conclusion

In this lesson, we explored two fundamental types of graph traversals. You learned the straightforward, degree-based rules for identifying Eulerian paths and circuits—a concept born from a classic puzzle. In contrast, you discovered the complexity behind Hamiltonian paths and cycles, understanding that while finding them is computationally hard, sufficient conditions like Dirac's and Ore's theorems can provide powerful guarantees.

Key Takeaways:

• Eulerian circuits/paths are all about edges. Their existence depends entirely on the parity of vertex degrees. This is an easy check and a common source of GATE questions.
• Hamiltonian cycles/paths are all about vertices. The general problem is NP-complete. For GATE, you must know the sufficient conditions given by Dirac's and Ore's theorems and understand that they are a one-way implication.
• To solve a problem, first identify whether it asks about edges (Eulerian) or vertices (Hamiltonian), then apply the corresponding rule or theorem.

In our next lesson, we will narrow our focus to a particularly important class of graphs: trees. Trees are connected graphs that contain no cycles. We will explore their unique properties, their different forms (like rooted and binary trees), and their critical role in computer science, including the concept of spanning trees.