Necessary Conditions

Graph Theory · Axiom Academy

LESSON Necessary Conditions for Hamiltonian Graphs Learn how to prove a graph is NOT Hamiltonian using necessary conditions The most basic necessary condition: A Hamiltonian graph must be connected . If a graph has multiple components, no cycle can visit all vertices because you cannot travel between disconnected parts of the graph. 2. No Cut Vertices in Hamiltonian Cycles A cut vertex (or articulation point) is a vertex whose removal disconnects the graph. While a Hamiltonian graph can have cut vertices in general, understanding their behavior is crucial. If removing a vertex creates too many components relative to what remains, the graph cannot be Hamiltonian. This is the most powerful necessary condition: In other words: removing k vertices can create at most k components. This is written as: Why this works: A Hamiltonian cycle must enter and exit each component. If you have more components than removed vertices, you don't have enough "connections" to link them all together in a single cycle. 4. Degree Conditions (Necessary Form) We've seen sufficient degree conditions (Dirac, Ore). The necessary condition is much weaker: This is obvious: a Hamiltonian cycle uses exactly 2 edges at each vertex (one entering, one leaving). While this seems weak, it's surprisingly useful for eliminating graphs with low-degree vertices. 5. Example: Proving Non-Hamiltonicity Let's apply the component condition to prove the Petersen graph is not Hamiltonian.

This is the written version of the interactive lesson above. See the full Graph Theory course.