Necessary Conditions
The conditions below are necessary for a graph to have a Hamiltonian cycle. That is: if any of them fails, then a Hamiltonian cycle does not exist.
- No leaf vertex: every vertex must have degree \( \deg(v) \ge 2 \).
- Connected graph: it must be possible to reach any vertex from any other vertex.
- No forced cut vertex: if removing a vertex disconnects the graph, that vertex would be a bottleneck that a cycle cannot bypass.
Important: “necessary” does not mean “sufficient”.
Even if all the conditions above are satisfied, a Hamiltonian cycle may still not exist.
Examples
Here are two quick counterexamples that violate necessary conditions and therefore cannot have a Hamiltonian cycle.
Example A — Vertex with degree 1
Vertex F has degree 1, so a Hamiltonian cycle cannot exist.
Example B — Disconnected graph
The graph has two components. Since it is not connected,
a Hamiltonian cycle cannot exist.