Recall that a simple graph is Hamiltonian (section 1.4) if there exists a cycle going through all the vertices: a Hamiltonian circuit.
In contrast with the Eulerian case (see corollary 1.44), it is a much more delicate task to handle the Hamiltonian situation (see example 2.8 about the NP-completeness of the problem). Therefore, unless P = NP, it is unlikely to get an “easy” characterization of Hamiltonian graphs. For pedagogical reasons (the arguments are easier to grasp), we first present a sufficient condition for Hamiltonicity given by Dirac, but this first result can be derived from stronger results that we present later on.
3.1. A necessary condition
The next result can be used to prove that some graphs are not Hamiltonian.
THEOREM 3.1.– If a simple graph G is Hamiltonian, then for every subset X of vertices, the number of connected components of the graph induced by V (G) \ X is less than or equal to the cardinality of X.
If we remove n (well-chosen) vertices and we get strictly more than n connected components in the resulting induced graph, then the original graph is not Hamiltonian. Consider the graph depicted in ...