Prove that in any simple graph $G$ with number of nodes $\geq 2$ there is at least one node $v$ that can be removed with its all edges, and keep the graph connected?
From my point of view I can say if there are nodes with a single edge then it can be removed without affecting the connectivity of the graph, and if there are two or more edges connected with a node, then we have at least a cycle, but a cycle can contain some removal nodes and some of non-removal. Could someone give me a concrete proof for this situation?
See the picture :
As we can see, it is possible to remove node A, or B, or C or D
Best Answer
Trees:
This is a tree, and, as you noted, there is a pendant vertex in the tree that can be removed without disconnecting the graph.
All other connected graphs:
Then this graph has a spanning tree, and you can remove one of the pendant vertices from the spanning tree. This clearly preserves some path between all the remaining vertices, because removing the pendant vertex does not disconnect the spanning tree.
There seems to be some confusion, so I'll illustrate the point with the image provided.
Take the subtree with edges $\{ab,bc,cd,ce\}$. We can see that in this tree, vertices $a$, $e$, and $d$ are pendant. As we demonstrated in the first case, removing one of these pendant vertices does not disconnect the subtree.
For example, if we delete $a$, then the rest of the graph ($\{b,c,d,e\}$) is still connected within the subtree, and so returning the other edges to it will not disconnect the graph.