Graphs such that $|G| \ge 2$ has at least two vertices which are not its cut-vertices Show that every graph $G$, such that $|G| \ge 2$ has at least two vertices which are not its cut-vertices.

Firstly, this question only makes sense if $G$ is connected.  So, assuming that $G$ is connected...

Let $H$ be a spanning tree of $G$ and let $l_1$ and $l_2$ be two leaf nodes of $H$.  Then $G \setminus \{l_1,l_2\}$ is connected.

We need to check:


*

*$G$ indeed has a spanning tree (since it's connected).

*$H$ has two leaf nodes (in fact, all trees on $\geq 2$ vertices have $\geq 2$ leaf nodes; this can be shown by induction).

*$G \setminus \{l_1,l_2\}$ is indeed connected.  This follows since $H \setminus \{l_1,l_2\}$ is a connected spanning subgraph of $G$.
