O'Reilly logo

Advanced Graph Theory and Combinatorics by Michel Rigo

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required