# Show that $G$ is $2$-connected but not necessarily Hamiltonian

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.

• Why do you think the Petersen graph is not $2$-connected? – mdp Oct 24 '14 at 12:45
• because I need to delete at least $3$ vertices to have it disconnected. No? – Diane Vanderwaif Oct 24 '14 at 12:48
• 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. – mdp Oct 24 '14 at 12:52
• 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). – Manuel Lafond Oct 24 '14 at 16:31