Eulerian and Hamiltonian Graphs

Eulerian and Hamiltonian Graphs

In graph theory, Eulerian and Hamiltonian graphs are two important types of graphs related to specific types of paths and cycles. These concepts have applications in optimization problems, circuit design, and network analysis.

1. Eulerian Graphs

An Eulerian graph is a graph in which there exists a path that visits every edge exactly once. This path is called an Eulerian Path. If the Eulerian path forms a cycle (i.e., it starts and ends at the same vertex), it is called an Eulerian Circuit.

Euler's Theorems:

Euler's theorems provide the conditions under which a graph has an Eulerian path or an Eulerian circuit:

• Eulerian Circuit: A graph contains an Eulerian circuit if and only if the graph is connected and every vertex has an even degree. This is known as Euler’s Theorem for Eulerian Circuits.

• Eulerian Path: A graph contains an Eulerian path if and only if the graph is connected and has exactly 0 or 2 vertices with an odd degree. This is known as Euler’s Theorem for Eulerian Paths.

In summary:

• A graph has an Eulerian circuit if all of its vertices have even degrees and it is connected.
• A graph has an Eulerian path if exactly two vertices have odd degrees and the graph is connected.

Example of an Eulerian Graph:

Consider the graph $G$:

   A --- B
   |     |
   D --- C

This graph has 4 vertices: $A, B, C, D$ and 4 edges. The degree of each vertex is 2, which is even. Therefore, this graph has an Eulerian Circuit, and the path could be:

$$A \to B \to C \to D \to A$$

This is an Eulerian Circuit because all edges are visited exactly once, and the path starts and ends at the same vertex.

---

2. Hamiltonian Graphs

A Hamiltonian graph is a graph that contains a Hamiltonian cycle, a cycle that visits every vertex exactly once and returns to the starting vertex. Unlike Eulerian graphs, the focus here is on visiting all vertices rather than all edges.

• A Hamiltonian cycle is a cycle that passes through every vertex exactly once and returns to the starting vertex.
• A Hamiltonian path is a path that passes through every vertex exactly once but does not necessarily return to the starting vertex.

There are no simple, universal theorems like Euler’s Theorem for Hamiltonian paths and cycles. The conditions for Hamiltonian cycles and paths are generally more complex, and there is no simple characterization like the degree conditions for Eulerian graphs.

Hamiltonian Path Problem:

Determining whether a graph contains a Hamiltonian path is a NP-complete problem. This means that it is computationally difficult to find a Hamiltonian path (or to determine if one exists) in large graphs.

Example of a Hamiltonian Graph:

Consider the following graph $G$:

   A --- B
   |     |
   D --- C

This graph has 4 vertices: $A, B, C, D$ and 4 edges. A possible Hamiltonian cycle could be:

$$A \to B \to C \to D \to A$$

This cycle visits every vertex exactly once and returns to the starting vertex, making the graph Hamiltonian.

---

Key Differences Between Eulerian and Hamiltonian Graphs

Property	Eulerian Graphs	Hamiltonian Graphs
Focus	Concerned with visiting every edge exactly once.	Concerned with visiting every vertex exactly once.
Eulerian Path	Exists if there are 0 or 2 vertices of odd degree and the graph is connected.	Not necessarily related to vertex degrees.
Eulerian Circuit	Exists if all vertices have even degree and the graph is connected.	A Hamiltonian cycle exists if there is a cycle that visits each vertex exactly once.
Conditions	Degree conditions: All vertices must have even degree for a circuit, exactly 2 odd-degree vertices for a path.	No simple degree condition. The problem is NP-complete.
Applications	Useful in problems like garbage collection routes, circuit board design.	Useful in solving problems like the Travelling Salesman Problem.

---

Algorithms and Computational Complexity

1. Eulerian Graphs:

   • Checking for Eulerian Path/Circuit: This can be done in linear time (O(V + E)) by checking the degree of each vertex and ensuring the graph is connected.

2. Hamiltonian Graphs:

   • Finding a Hamiltonian Path or Cycle: This is generally a NP-complete problem, meaning there is no known efficient algorithm for solving it in all cases. It may require exhaustive search techniques, such as backtracking, or approximation methods.
   • Special Cases: There are some polynomial-time algorithms for specific types of graphs (e.g., complete graphs, bipartite graphs) where Hamiltonian cycles can be found more efficiently.

---

Examples of Graph Types and Their Eulerian/Hamiltonian Properties

1. Complete Graphs (Kₙ):

   • A complete graph $K_n$ is Eulerian if $n$ is even (since every vertex has degree $n-1$, which is even for even $n$).
   • A complete graph $K_n$ is Hamiltonian for all $n \geq 3$ (since it contains a cycle that visits all vertices).

2. Cycle Graphs (Cₙ):

   • A cycle graph $C_n$ is always Eulerian (since every vertex has degree 2).
   • It is also Hamiltonian since it contains a cycle that visits all vertices.

3. Tree Graphs:

   • A tree with more than 2 vertices is not Eulerian (because it has vertices with odd degrees).
   • A tree is not Hamiltonian unless it has exactly 2 vertices (because it cannot form a cycle with more than 2 vertices).

---

Conclusion

• Eulerian Graphs focus on paths and circuits that visit every edge exactly once, and they have well-defined degree conditions for having an Eulerian path or circuit.
• Hamiltonian Graphs focus on paths and cycles that visit every vertex exactly once, but there are no simple degree conditions for determining whether a graph contains a Hamiltonian path or cycle. The problem of finding such paths and cycles is NP-complete.

Understanding these graph properties is essential for various applications, including optimization problems, network routing, and circuit design.