Let $G$ be a graph of order $n\geq 3$ having property that for every vertex $v$ of $G$, there is a Hamiltonian path with initial vertex $v$. Show that $G$ is $2$-connected but not necessarily Hamiltonian (i.e. needn't contain a Hamiltonian cycle).

The book told me to consider the Petersen graph, but I don't think the Petersen graph is $2$-connected.

  • $\begingroup$ Why do you think the Petersen graph is not $2$-connected? $\endgroup$ – mdp Oct 24 '14 at 12:45
  • $\begingroup$ because I need to delete at least $3$ vertices to have it disconnected. No? $\endgroup$ – Diane Vanderwaif Oct 24 '14 at 12:48
  • 1
    $\begingroup$ Yes - this is fine! A graph is $n$-connected if you can delete any $k<n$ vertices without disconnecting it, so any $n$-connected graph is also $m$-connected for $m\leq n$. The Petersen graph is $3$-connected, hence $2$-connected. $\endgroup$ – mdp Oct 24 '14 at 12:52
  • 1
    $\begingroup$ And if you want it to be not 3-connected, you can remove edges from it until it is only 2-connected (as removing edges from a non-hamiltonian graph cannot make it hamiltonian). $\endgroup$ – Manuel Lafond Oct 24 '14 at 16:31

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.