18.1 Hamiltonian and Nonhamiltonian Graphs

Theorem 18.1

• $G$
  • hamiltonian graph
• $S \subseteq V(G)$,

Then

\[\begin{eqnarray} c(G - S) \le \|S\| \label{chap_18_01_hamiltonian_graph} \end{eqnarray} .\]

proof

Let $C$ be a Hamilton cycle of $G$.

Since $C$ is a cycle, $C - S$ has at most $|S|$ components. $G - S$ has more edges than $C - S$ so $G - S$ has at most $|S|$ components.

$\Box$