Hamiltonicity Necessary Condition (Components after Vertex Deletion)

If G is Hamiltonian then deleting any set S of vertices leaves at most |S| connected components: c(G-S) ≤ |S|. Deleting many vertices and counting components that shatter is the fastest way to prove a graph is NOT Hamiltonian.