Proof that any simple connected graph has at least 2 non-cut vertices.

Solution 1:

I think the result follows from the fact that every connected graph has a spanning tree and every tree with more than one vertex has at least two leaves.

(By the way, if you want to prove this by induction on $k$, then in Step 3 you shouldn't start with a $k$-vertex graph and add a vertex to it. You're trying to prove some property of $(k+1)$-vertex graphs, so you need to start with a $(k+1)$-vertex graph; then you might choose to take one vertex away and use the induction hypothesis.)

Solution 2:

Let $G$ be a connected graph of order 3 or more, and let $u$ and $v$ be two vertices of $G$ whose distance from one another, $l$, is equal to the diameter of $G$, $d(u,v) = diam(G)=l$. We claim that neither $u$ nor $v$ are cut-vertices of $G$.

Assume, to the contrary, that one of $u$ and $v$, say $u$, is a cut-vertex of $G$. Then, in $G-u$, there is a vertex $x$ in a different component from $v$. Thus, in $G$, $u$ lies on every $v-x$ path.

Now, let $P$ be a shortest $v-x$ path in $G$. Since $P$ contains $u$, $d(v, x) > d(v,u)$ which is impossible.