Hamilton Graph is 2-connected

Question

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.

Answer 1

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.

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.

Answer 2

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.