# 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 O’Reilly online learning.

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