# 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.

-

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.

-

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$.

-