Eular's graph and Hamiltonian graph

 Eulerian and Hamiltonian graphs are two important concepts in graph theory related to traversing graphs in specific ways.

Eulerian Graphs

A graph is Eulerian if it contains an Eulerian circuit—a closed path that visits every edge exactly once.

Eulerian Circuit (or Eulerian Cycle)

• A cycle (closed path) that traverses every edge exactly once and returns to the starting vertex.

Eulerian Path (or Eulerian Trail)

• A path that visits every edge exactly once but does not necessarily return to the starting vertex.

Eulerian Graph Theorem

• A connected graph has an Eulerian Circuit if and only if all vertices have even degrees.
• A connected graph has an Eulerian Path if and only if exactly zero or two vertices have odd degrees.

Example of Eulerian Graph

A simple example is a cycle graph where each vertex has an even degree.

---

Hamiltonian Graphs

A graph is Hamiltonian if it contains a Hamiltonian cycle—a closed path that visits every vertex exactly once.

Hamiltonian Cycle

• A cycle (closed path) that visits each vertex exactly once and returns to the starting vertex.

Hamiltonian Path

• A path that visits each vertex exactly once but does not necessarily return to the starting vertex.

Hamiltonian Graph Theorem (Necessary Conditions)

• Unlike Eulerian graphs, there is no simple necessary and sufficient condition for Hamiltonian graphs. However, some useful conditions include:
  1. Dirac’s Theorem: If a graph with $n$ vertices ($n \geq 3$) has each vertex with a degree of at least $n/2$, then the graph is Hamiltonian.
  2. Ore’s Theorem: If for every pair of non-adjacent vertices $u$ and $v$, the sum of their degrees is at least $n$, then the graph is Hamiltonian.

Example of Hamiltonian Graph

A complete graph $K_n$ is always Hamiltonian because there exists a cycle that visits every vertex exactly once.

---

Key Differences Between Eulerian and Hamiltonian Graphs

Feature	Eulerian Graph	Hamiltonian Graph
Path Type	Eulerian Path (covers all edges once)	Hamiltonian Path (covers all vertices once)
Cycle Type	Eulerian Cycle (returns to start, covers all edges once)	Hamiltonian Cycle (returns to start, covers all vertices once)
Necessary Condition	All vertices have even degree (Eulerian Circuit) or at most two odd-degree vertices (Eulerian Path)	No simple condition, but degree constraints help (e.g., Dirac’s Theorem)
Focus	Edges	Vertices