# Find Hamiltonian cycle

Suppose $$G$$ is a simple graph with order $$n$$, the minimum degree $$\delta\geq \frac{n+q}{2}$$, prove that for any pairwise non-adjacent $$q$$ edges, there exists a Hamiltonian cycle $$H$$ contains these edges.

I want to choose a Hamiltonian cycle $$H'$$ contains these edges as much as possible, then define $$S$$ and $$T$$ such that $$n+q\leq d(u)+d(v)=|S|+|T|=|S \cup T|+|S\cap T|\leq n+q-1$$ to induce contradiction, but I don't know how to define $$S$$ and $$T$$, could anyone help me?

Contract all $$q$$ edges to get $$G’$$. $$G’$$ has order $$n-q$$ and minimum degree $$\delta ‘ \geq \frac{n-q}{2}$$ since it cannot decrease more than the order did. Since the minimum degree is at lest half the order, $$G’$$ is Hamiltonian as proven by Dirac.