Uniqueness of hamiltonian cycle Let G be a graph on $n$ vertices, where $n \geq 8$ and with minimum degree at least $n/2$. Does $G$ have at least 2 distinct Hamilton cycles? (Two Hamilton cycles are said to be distinct if they differ in at least 1 edge).
I think this statement is true. I thought I could prove it using a maximal counterexample, where adding 1 edge would create a second Hamilton cicle and then follow the proof of Ore's theorem. However, that did not work out. Does anybody have an idea how to proof or refute this statement?
 A: This can be shown using the Bondy–Chvátal theorem, which states that a graph $G$ is Hamiltonian if and only if $G + uv$ is Hamiltonian, where $u,v$ are nonadjacent vertices of $G$ with $d(u) + d(v) \geq n$.
To see this, take a Hamiltonian cycle $C$ of $G$ (guaranteed to exist by Dirac's theorem or its generalizations) and an edge $uv \in C$. We want to show that $G - uv$ is Hamiltonian. Now the Bondy-Chvátal theorem allows us to add every edge $xy$ with $x,y \notin \{u,v\}$ to $G-uv$, so that $G-\{u,v\}$ becomes a complete graph. But then the same theorem allows us to add all edges of the form $ux$ and $vx$ for $x \notin \{u,v\}$, and finally to add $uv$ back into the graph. In the end, we are left with a complete graph, which is, of course, Hamiltonian.
In fact, what we have shown is that $G-e$ is Hamiltonian for any edge $e$. You can use the same argument to show that you can leave about $n/4 - 1$ edges (I didn't check the precise number) and thus find that many different Hamiltonian cycles.
