Hamiltonian paths and cycles
Graph theory · Mathematics
Study notes
Q: A 5-vertex graph: every vertex has degree ≥ 3. Must it have a Hamiltonian cycle? n = 5, n/2 = 2.5. All degrees ≥ 3 > 2.5. Dirac's theorem: deg ≥ n/2 for all → Hamiltonian cycle GUARANTEED! Yes - some cycle visits all 5 vertices exactly once.