# Hamiltonicity, induction.

• Feb 11th 2013, 03:07 AM
Olotila
Hamiltonicity, induction.
I am going trough a proof, stuck in induction. Sentence is here, end of page 301.

Formatting is in latex (how can I make it look better in this math forum?).

Some definitions:

$G$ is a non-hamiltonian 2-connected graph, $C$ is a cycle in $G$, $D$ is a component of $G-C$ and $C$-trail is either a $C$-path or a cycle meeting $C$ in exactly one vertex.

Square of a graph $G$ (denoted by $G^2$) is a graph in which two vertices are adjacent if and only if they have distance at most 2 in $G$. That means $G^2$ is "created" from $G$ by adding an edge connecting vertices whose distance is at most 2.

If $D$ consists of a single vertex $u$, we pick any $C$-trail in $G$
containing $u$, and let $E_D$ be the set of its two edges. If $|D| 1$, let $\tilde{D}$ be the (2-connected) graph obtained from $G$ by
contracting $G−D$ to a vertex $\tilde{x}$. Applying the induction
hypothesis to $\tilde{D}$, we obtain a Hamilton cycle $\tilde{H}$ of
$\tilde{D^2}$ whose edges at $\tilde{x}$ lie in $E(\tilde{D})$.

What exactly is "the induction hypothesis" here?