Graph Theory – Proving Every Connected Graph Has a Removable Vertex

Question

I have not done much proofs before this and need some guidance. I know that for a simple graph such as this :

node - node - node -node

Removing the first and last vertex will not disconnect the graph. So far, I can think of two cases: Where there are leaves, or nodes with degree of 1. Where there are no leaves, which means all nodes have degrees 2 or more.

In the first case, removing the leaf will not disconnect the graph. In the second case, removing any should not disconnect the graph. Problem is, I don't know how to formulate this into a good proof.

Answer 1

Remove a leaf of a spanning tree.