0
$\begingroup$

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.

enter image description here

Though, this is not exactly what the problem asks. Any idea how to prove the above statement?

EDIT:

enter image description here

$\endgroup$
  • $\begingroup$ In a Hamiltonian graph there is a cycle containing all vertices. $\endgroup$ – Leen Droogendijk Oct 28 '15 at 15:32
  • $\begingroup$ I know this fact, though I'm having difficulties in seeing how this will help me. $\endgroup$ – user72151 Oct 28 '15 at 15:35
1
$\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$
  • $\begingroup$ I can see this using my modified graph. So whichever vertex I remove, I still get a one connected component. Though, what I don't understand is, according to me the problem what's me to prove that any Hamiltonian graph is 2-connected, am I wrong? Because, let's say if we get the graph composed of 4 vertices, and which has the form of a square, I can have a cycle by simply going through the path $1-2-3-4-1$, which means it is Hamiltonian. But, if I remove one of the vertexes, I will have a disconnected graph. $\endgroup$ – user72151 Oct 28 '15 at 15:55
  • 1
    $\begingroup$ No, if you remove one vertex, you still have a connected graph, e.g. if you remove vertex 3, the remaining graph contains the path $412$ and is still connected. $\endgroup$ – Leen Droogendijk Oct 28 '15 at 17:26
0
$\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$

Your Answer

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