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.
 A: Let $P$ be a maximal path in $G$. I claim that the end points of $P$ are not cut vertices. 
Suppose that an end point $v$ of $P$ was a cut vertex. Let $G$ be separated into $G_1,\ G_2,\ \cdots,\ G_k$. It follows that any path from one component to another must pass through $v$ and namely such a path does not end on $v$ and therefore cannot be $P$. Therefore $P$ is contained entirely within some $G_i\cup\{v\}$. But this contradicts the fact that $P$ is maximal for there exists at least one vertex in $G_j$ for $i\neq j$ which connects to $v$ and extends $P$. Therefore $v$ must not be a cut vertex.
A: 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$.
A: I think Douglas' answer is good except the very first line: 
G doesn't have to be connected for this question to make sense. 
For a disconnected graph G, the argument could be applied to any connected component of G WLOG. If you can prove that a pair of leaves exists that satisfy the condition for a connected graph (as Douglas does), the same must be true for a connected subgraph of a disconnected graph. 
Note also: for the smallest possible $G$ (consisting of 2 vertices and 0 edges), you simply have two isolated vertices. If you remove both of the vertices from such graph, you have an empty graph (not an increased number of connected components). So the theorem still holds.
