Given a sparse graph, how can one go about proving that it is Hamiltonian? (Assuming it actually is, of course).

There are three main classes of criteria for Hamiltonicity that I am aware of:

Dirac-type conditions ($\delta \geq \frac{n}{2}$, i.e. high minimum degree).

Spectral conditions.

Erdos-Chvatal-type conditions ($\kappa \geq \alpha$, i.e. connectivity greater than independence number).

However, none of these approaches is able to settle even the Hamiltonicity of $C_{n}$, the $n$-cycle! Apparently, the reason is that these approaches work best for dense graphs.

Is there an alternative criterion that works well for sparse graphs?

twoadditional vertices to the $C_n$ in that way. – Wolfgang Jan 30 '14 at 20:23