Given a graph $G$ with no cut-vertices, does it directly imply that $G$ is Hamiltonian?

It is known that if a graph $G$ is nonseparable (thus, no cut-vertices) then every two distinct vertices in $G$ lies in a common cycle.

Is it ALWAYS possible that the cycle referred to that result is a Hamiltonian cycle?


  • 2
    $\begingroup$ False. See the Petersen graph. $\endgroup$ – Parcly Taxel Oct 16 '16 at 9:14
  • $\begingroup$ Oh yes. I forgot that one. Thanks $\endgroup$ – mathislove Oct 16 '16 at 9:17

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.