I want to prove that: for any simple, connected graph there is at least one node whose removal results in a connected graph. Here is my proof:
- Suppose that a graph $G$ is simple connected graph with $\delta(G)$ is the minimum degree of the vertices. If $\delta(G)=1$ then there is a node with one edge, and removing this node with its edge keeps $G$ connected
If $\delta(G) \ge 2$, then $G$ cannot be a tree, and we must have a cycle in the graph $G$, as every tree has at least two leaves which means $\delta(G) =1$ for trees. Now suppose that the cycle is defined as $C= (v_0,v_1,\cdots,v_k,v_0)$. Then, removing the node $v_i$ from $C$ where $deg(v_i)$ is the lowest degree of the nodes in this cycle will certainly keep the graph connected.
This concludes the proof.
Is this a correct and complete proof?