Advanced Graph Theory and Combinatorics

3Hamiltonian Graphs

In this chapter, we will only consider simple graphs. So we are dealing with the unoriented case and since we are searching for a circuit visiting once every vertex of the graph, there is no need to consider loops or multiple edges.

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 ...