A non-complete graph is called 2-connected if it stays connected after removing a vertex (and all edges which are incident to that vertex). Show that a Hamiltonian graph is 2-connected.
I'm having difficulty in proving the above statement. I already found in a lot of places that says that if a graph is Hamiltonian than it is 2-connected. Though, I know that if a graph is 2-connected it doesn't necessarily mean that it is Hamiltonian. For example, I came up with the graph below, which is 2-connected, I mean removing the vertex 3, still leaves the graph connected, but the graph is not Hamiltonian.
Though, this is not exactly what the problem asks. Any idea how to prove the above statement?
EDIT:
2 Answers
$\begingroup$In a Hamiltonian graph there is a cycle containing all vertices. When you remove one vertex from this cycle, the remaining graph contains a path with all the remaining vertices. Since a path is connected this proves the claim.
$\endgroup$ 2 $\begingroup$One of the necessary conditions for any graph G to be Hamiltonian,is that w(G-S)≤|S|,for any subgraph of G Let's go about this using proof by contradiction by assuming that a Hamiltonian graph is not 2 connected If this were so then there exists a vertice v such that when v is removed from G,G is no longer connected ,that is G has more than one connected component This vertice is a subgraph with |S|=1 But since there's more than one connected component in G-S,w(G-S)>1 This violates the necessary condition w(G-S)≤|S| Thus G has to be 2-connected for the graph to be Hamiltonian
$\endgroup$
