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?
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.