Eulerian and Hamiltonian Paths

Eulerian and Hamiltonian Paths

In graph theory, Eulerian and Hamiltonian paths are two distinct types of paths that have specific properties related to the traversal of a graph. Understanding these paths is important in applications like circuit design, routing, and network analysis. The key difference between the two lies in how the vertices and edges are used during the traversal.

1. Eulerian Path and Circuit

An Eulerian path in a graph is a path that visits every edge of the graph exactly once. An Eulerian circuit (or cycle) is an Eulerian path that starts and ends at the same vertex.

a) Conditions for an Eulerian Path

For an undirected graph to have an Eulerian path, the following conditions must hold:

1. Exactly 0 or 2 vertices have an odd degree.
2. All the vertices with nonzero degree are connected (the graph must be connected when considering only the vertices with edges).

• If there are exactly 0 vertices with odd degrees, then the graph contains an Eulerian circuit (which is also an Eulerian path).
• If there are exactly 2 vertices with odd degrees, the graph contains an Eulerian path but no Eulerian circuit.

b) Conditions for an Eulerian Circuit

For an undirected graph to have an Eulerian circuit, the following conditions must hold:

1. All vertices must have an even degree.
2. The graph must be connected when considering only the vertices with edges.

If a graph satisfies these two conditions, it contains an Eulerian circuit.

Example:

Consider the graph with vertices $A, B, C, D$ and edges $AB, BC, CD, DA, AC$.

• All vertices have an even degree, so this graph contains an Eulerian circuit.
• A possible Eulerian path might be $A \rightarrow B \rightarrow C \rightarrow D \rightarrow A$.

Applications of Eulerian Paths and Circuits:

1. Chinese Postman Problem: The goal is to find the shortest path that visits every edge of a graph (usually a road network) at least once. The problem is closely related to finding Eulerian paths and circuits.
2. Network Routing: Efficiently routing tasks or packages through a network where every connection (edge) needs to be visited exactly once.

2. Hamiltonian Path and Circuit

A Hamiltonian path is a path that visits every vertex of the graph exactly once. A Hamiltonian circuit (or cycle) is a Hamiltonian path that starts and ends at the same vertex.

a) Conditions for a Hamiltonian Path

Unlike Eulerian paths, there is no simple characterization or formula for when a graph has a Hamiltonian path. In general, finding a Hamiltonian path is more complex and does not depend solely on vertex degrees.

However, some heuristics and theorems provide useful conditions or approaches:

• Dirac's Theorem: A graph with $n \geq 3$ vertices is Hamiltonian-connected if every vertex has a degree of at least $n/2$.
• Ore’s Theorem: A graph with $n \geq 3$ vertices is Hamiltonian-connected if for every pair of non-adjacent vertices, the sum of their degrees is at least $n$.

b) Conditions for a Hamiltonian Circuit

Similarly, the conditions for a Hamiltonian circuit are more complex and involve graph-specific analysis. However, sufficient conditions can be used for specific types of graphs.

• Dirac’s Theorem: If every vertex in a graph has degree at least $n/2$, then the graph contains a Hamiltonian cycle (if $n \geq 3$).
• Chvátal’s Theorem: A graph is Hamiltonian if it satisfies certain degree conditions that relate to its vertex degrees.

Example:

Consider a graph with vertices $A, B, C, D, E$, and edges $AB, BC, CD, DA, AC, BD, BE, CE$.

• A possible Hamiltonian path might be $A \rightarrow B \rightarrow D \rightarrow C \rightarrow E$.
• A possible Hamiltonian circuit might be $A \rightarrow B \rightarrow D \rightarrow C \rightarrow E \rightarrow A$.

Applications of Hamiltonian Paths and Circuits:

1. Traveling Salesman Problem (TSP): This problem seeks to find the shortest Hamiltonian circuit that visits every city (vertex) exactly once and returns to the starting city. The TSP is a famous optimization problem in logistics and planning.
2. Routing and Scheduling: In various scheduling and routing problems, finding Hamiltonian paths and circuits is essential to minimize time or distance.
3. Circuit Design: Hamiltonian circuits may be used in circuit design problems, such as minimizing the number of wiring paths in chip layout.

3. Differences Between Eulerian and Hamiltonian Paths

4. Complexity of Finding Eulerian and Hamiltonian Paths

• Eulerian Path: Determining if a graph has an Eulerian path can be done in linear time, $O(V + E)$, by checking the degree conditions and ensuring the graph is connected. Once these conditions are satisfied, constructing the Eulerian path is straightforward.

• Hamiltonian Path: Finding a Hamiltonian path is much more computationally difficult. The problem is NP-complete, meaning there is no known polynomial-time algorithm to solve it for all graphs. For large graphs, brute-force algorithms or approximation methods are often used. Techniques like backtracking, dynamic programming, or heuristic methods may help solve specific instances.

5. Summary

• Eulerian Paths:

  • Visit every edge of the graph exactly once.
  • For an Eulerian path, the graph must have exactly 0 or 2 vertices with an odd degree.
  • An Eulerian circuit is a cycle that visits every edge exactly once and returns to the starting vertex.

• Hamiltonian Paths:

  • Visit every vertex of the graph exactly once.
  • There is no simple condition for determining the existence of a Hamiltonian path, unlike Eulerian paths.
  • A Hamiltonian circuit is a cycle that visits every vertex exactly once and returns to the starting vertex.

Both types of paths are crucial in many practical applications, including routing, network design, and optimization problems. Eulerian paths are easier to identify and compute, while Hamiltonian paths pose more computational challenges, often requiring advanced algorithms and heuristics.