a cycle of length $|V(G')| - 2$.

For $C =1$ and $C \geq 4$ odd, let $H$ be the disjoint union of $G'$ with an arbitrary $3$-regular graph on $C-1$ (even) vertices and for $C=2$ let $H = G'$. Then $H$ has a cycle of length at least $n - C$ if and only if $G$ has a Hamilton cycle.

\(ii) We reduce to the problem of deciding the existence of a Hamilton path in general graphs, which is known to be NP-complete [@Garey]. Given a graph $G$ on $k$ vertices, construct the graph $H$ as follows. Start by taking a complete bipartite graph with bipartition $V(H) = A \cup B$ where $|A| = 1 + r$ and $|B| = (C+1)k + r$ and $r$ is chosen so that $|A| / (|A| + |B|) > \alpha$. Now we insert $C+1$ disjoint copies of $G$ into $B$ to form $H$. Note that $\delta(H) \geq \alpha |V(H)|$ and it is easy to see that $H$ has a cycle of length $|V(H)| - C$ if and only if $G$ has a Hamilton path. This gives the desired reduction since $|V(H)|$ is linear in $|V(G)|$.

Preliminaries {#sec:notation}
=============

We follow general graph theory notation 