Dirac's & Ore's Theorems, and Why Hamilton Circuits Are Hard | Discrete Mathematics §10.5

Since there's no clean test for a Hamilton circuit, mathematicians settled for the next best thing: conditions that guarantee one exists. Dirac's and Ore's theorems say that if a graph is dense enough, a Hamilton circuit must be there. In this video: sufficient conditions and the hardness of the problem, on the board. Dirac's theorem: if every vertex has degree at least n/2, the graph is Hamiltonian — checked on a wheel. Ore's theorem: if every pair of non-adjacent vertices has degrees summing to at least n. We stress these are sufficient but not necessary — the 5-cycle fails both yet is Hamiltonian. Then the hardness: deciding Hamiltonicity is NP-complete, roughly n-factorial work, illustrated with a small Traveling Salesman tour and a nod to Gray codes on the cube. This video is part of Discrete Mathematics · Graphs (§10.5 — Euler & Hamilton Paths). Full section playlist linked above / in the description on the channel. Made with the Engineering Simplified method: a calm, two-voice story lesson taught on a chalk-and-board, with every definition and example drawn out step by step. Topic coverage follows Rosen, Discrete Mathematics and Its Applications (Chapter 10).