Proof verification: a connected graph always has a vertex that is not a cut vertex

Question

Prove that every connected graph has vertices that even when you remove them, the graph stays connected.

Let's assume that $\delta(G)>1$ because if it is equal to 1, the proof is trivial.

I will use a Lemma that says that if $\delta(G)>1$ then there is a cycle (no need to prove here because I proved it in another task).

$(1)$ Let's find that cycle and call it $C=v_1,v_2,...,v_k$.

$(2)$ Now let's remove one of the $v_i$ where $i=1,2,...,k$. If the graph stays connected - end of the proof. If not:

$(3)$ let's go back to the full $C$ cycle and remove $v_j$ where $i\neq j$. If now the graph is connected - end of proof. If not repeat step $(3)$ and remove $v_z$ where $i\neq j \neq z$. Repeat until we find proper $v$ every time removing different $v_i$. We will find it eventually.

Let's assume we didn't. That means that for every $v_i$ removed from the cycle, our graph becomes disconnected. That means that in our cycle there were to vertices, let's call them $v_n$ and $v_m$ that the cycle looked like: $v_1,...,v_n,v_m,v_n,..$ and that's contradiction to the definition of a cycle and indeed there exists a vertex that you can remove without making the graph disconnected.

I know it may look bad, but is it correct? If not, I would be glad for another proof or for showing me where I made mistake(s).

Answer 1

Counter argument to outline the incorrectness of the statement you numbered as (3):

Imagine you have a circle, and on that circle spread equally 10 points. Outside the circle draw 10 points and connect each of the outside point to exactly one point on the circle that is not connected to any other point outside the circle. The points on the circle determine a cycle, and you can see that if you remove any one point from the cycle you get a disconnected graph.

Proof of the statement:

If we have a node of degree one, then removing it gives a connected graph. Otherwise, every path in the graph belongs to a cycle(To see this, start with any path, then see that the terminal nodes of this path must be connected to other nodes that are not in the path, so adding them to the path makes again a path...continuing this process you can see that in the end we will add all nodes from the graph to the path). If among all those paths there is no path from which one can remove a node, without disconnecting the graph, then all those paths are bridges, hence they do not belong to a cycle, which is a contradiction. (This is, assuming that your graph is finite)

Answer 2

Your proof doesn't seem correct because you could have a cycle and then have one edge going out to a distinct connected component for every vertex in the cycle. Then it's possible that you will always get a disconnected graph when you remove each of the vertices in the cycle. Or am I missing something about what $\delta(G) > 1$ means?

Answer 3

I find it easier to show that there are at least two such vertices for $n \geq 2$, using induction.

You can verify easily, as a base case, that every connected graph on 2 vertices has at least two vertices that don't disconnect the graph.

Now take a connected graph $G$ with $n$ vertices, assuming the statement holds for every connected graph with less than $n$ vertices.

If $G$ has no vertex that disconnects it upon removal, you're done. Otherwise say there is such a vertex $v$. Then $G - v$ has at least 2 connected components $G_1$ and $G_2$. We show that both have a vertex that don't disconnect $G$. Take $G_1$ without loss of generality. If $G_1$ has only one vertex, it is a degree one vertex in $G$ and it can be removed.

Otherwise, by induction, $G_1$ has two vertices $u_1, u_2$ that don't disconnect it. If none of $u_1, u_2$ disconnect $G$, you're done. So suppose removing $u_1$ disconnects $G$. Then $u_1$ is the only neighbor of $v$ that lies in $G_1$, or otherwise $v$ would connect $G_1 - u_1$ to the rest of the graph. So $u_2$ doesn't disconnect $G$, as $v$ is connected to $G_1 - u_2$ through $u_1$. Applying the same argument to $G_2$ yields two vertices that don't disconnect $G$ when removed.

Answer 4

DFS visits every vertex in a connected graph, and there always will be an unmarked vertex that is visited last.

It can be removed without disconnecting the graph because the DFS was able to reach all other vertices without visiting the last vertex.