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?
Best Answer
No. You misunderstood the definition of 2-connected. This says that you can't remove a vertex such that the graph becomes unconnected. You have merely proven that there exists a vertex that can be removed such that the graph remains connected.
The claim is not true either. For this, consider the 3-path.