Eulerian and Hamiltonian graphs are key concepts in graph theory. Eulerian graphs focus on traversing all edges, while Hamiltonian graphs aim to visit all vertices. These ideas have important applications in network design and optimization.
Eulerian graphs have clear conditions and efficient algorithms. In contrast, Hamiltonian graphs are more complex, with no complete characterization. Understanding these differences helps grasp the varying difficulty levels in graph theory problems.
Eulerian Graphs
Conditions for Eulerian graphs
- Eulerian circuit traverses closed trail visiting every edge exactly once requires connected graph with all vertices having even degree
- Eulerian trail traverses path visiting every edge exactly once needs connected graph with exactly two vertices having odd degree and all others even degree
Proof of Eulerian conditions
- Necessity proof assumes graph has Eulerian circuit implying vertices entered and exited equal number of times resulting in even degree for all vertices
- Sufficiency proof assumes connected graph with all vertices of even degree uses induction on number of edges starting with base case of graph with no edges being Eulerian then removes any cycle and recurses on remaining graph
Vertex degrees in Eulerian circuits
- Sum of vertex degrees in any graph always even
- Eulerian circuit mandates all even degrees
- Eulerian trail permits exactly two odd degree vertices serving as start and end points
- Handshaking lemma states $\sum_{v \in V} \deg(v) = 2|E|$ (total degree equals twice number of edges)
Hamiltonian Graphs
Complexity of Hamiltonian graphs
- Hamiltonian cycle problem classified as NP-complete lacking known polynomial-time algorithm for general graphs
- Contrasts with Eulerian graphs solvable in polynomial time
- No complete characterization of Hamiltonian graphs exists only necessary or sufficient conditions
- Hamiltonian cycle visits every vertex exactly once (Königsberg Bridge Problem)
Sufficient conditions for Hamiltonian graphs
- Dirac's theorem provides sufficient condition for Hamiltonicity stating graph G with n ≥ 3 vertices and minimum degree δ(G) ≥ n/2 is Hamiltonian
- Ore's theorem generalizes Dirac's theorem asserting graph G with n ≥ 3 vertices and deg(u) + deg(v) ≥ n for all non-adjacent vertices u and v is Hamiltonian
- Bondy-Chvátal theorem introduces closure of graph adding edges between non-adjacent vertices u, v if deg(u) + deg(v) ≥ n proving graph is Hamiltonian if and only if its closure is Hamiltonian