3Hamiltonian Graphs

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

Get Advanced Graph Theory and Combinatorics now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.