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).
Best Answer
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.