Let $n$ be the number of the vertices of a graph $G$. If the degree of each vertex of $G$ is at least $\frac{n+1}{2}$, prove that for an edge $e$ of $G$ there is a Hamiltonian cycle containing $e$.

I know that the theorem which says that if for every two vertices $x,y$ of a graph, $d(x)+d(y)\ge n$ then there is a Hamiltonian path. I tried to use the idea of the proof of this theorem, using maximal paths, but I could not conclude this assertion.

  • 2
    $\begingroup$ Look up a proof of Ore's theorem (the theorem which you cite). Part of the proof actually shows that, under certain conditions, given any $u,v\in V$, you can find a Hamilton path that starts at $u$ and ends at $v$. This will imply your claim $\endgroup$ – munchhausen Jun 24 '18 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.