Show that a Hamiltonian graph is 2-connected. But the reverse is not true. Give an example for reverse.

This guestion is my profesor's. I'm having difficulty in proving the above statement. Hoew can I shot that? Can you help me. Thank you.

  • $\begingroup$ Take a Hamiltonian circuit. If you remove a point, you still have a path that visits every vertex (prove this). Hence the new graph is connected. $\endgroup$ – Charles Hudgins Apr 12 at 18:08
  • $\begingroup$ This idea for reverse? $\endgroup$ – glemisanki Apr 12 at 18:20

As pointed out in the comments, it is easy to see that a Hamiltonian graph is $2$-connected. The Petersen graph furnishes an example of a $2$-connected graph that is not Hamiltonian.

enter image description here
There is a Hamilton path starting at any vertex, as shown below. The red path is a Hamilton path starting at vertex D. So, if we delete vertex D, the graph is still connected.

There is an isomorphism of $G$ to itself, carrying any vertex to any other vertex. For the vertices on the outer pentagon, a rotation of the diagram gives an example. Also, it's easy to check that the map that exchanges a vertex on the pentagon with its neighbor on the inner star is an isomorphism. Now rotation gives an isomorphism carrying any vertex to the pentagon to any vertex on the star.

This implies that there is a Hamilton path starting at any vertex, so deleting any vertex leaves the graph connected.

It is well-known that the Petersen graph is not Hamiltonian. One way to prove this is to try to three-color the edges so that no two edges of the same color meet at a point. We find by trial that this is impossible. Now, if the graph were Hamiltonian, since there are $10$ vertices, we could color them alternately red an blue. Since each vertex is of degree $3$, there is one uncolored edge at each vertex, and we could color them all green, giving a proper $3$-coloring of the edges.

  • 4
    $\begingroup$ Another handy example of a $2$-connected graph which is not Hamiltonian is the complete bipartite graph $K_{2,3}$. (Or any other $K_{m,n}$ with $m,n \ge 2$ and $m \ne n$.) $\endgroup$ – Misha Lavrov Apr 12 at 19:44

I think the definition of $k$-connected that would help you most is this: a graph with at least two vertices is $k$-connected if, for every pair of vertices, there are at least $k$ vertex-disjoint paths.

Since the graph is Hamiltonian, we know there is a cycle that contains every vertex. Well, then you can find two vertex-disjoint paths between every vertex in the graph.

However, the reverse is false because removing a vertex may leave the graph without cycles.

  • 1
    $\begingroup$ The definition of $k$-connected is that there are at least $k$ internally vertex-disjoint paths between any pair of vertices. There may be more. (Also, your example for the reverse does not make sense: you are looking for a $2$-connected graph which is not Hamiltonian, but $P_{n-2}$ is neither, and $C_n$ is both.) $\endgroup$ – Misha Lavrov Apr 12 at 19:43
  • $\begingroup$ Oh my, sorry about the definition, that was typo. Already corrected. As for the reverse, you are right, I wasn't thinking straight. I removed the example, could you give a counter-example? $\endgroup$ – Lucas Peres Apr 12 at 20:58
  • $\begingroup$ Just saw you other comment. A $K_{2,3}$ will do. Thanks! $\endgroup$ – Lucas Peres Apr 12 at 20:59

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.