Prove that for all trees G = (V, Ε) and all vertices $c\in V$, if υ has at least two neighbours, then ν is a cut vertex of G using induction.

Question

I'm having difficulties rigorously proving the inductive step. For example, since i can assume G has a vertice of at least degree 2, can i let an arbitrary vertice, say $v_k$, be a vertex that forms an edge with u. Then since G is not a cycle, if i remove u there is no way for $v_k$ to form a path with the other neighbor(s) of the previous u, say $v_{k+1}$.

Answer 1

The induction step :

Let $G$ be a graph with $n+1$ vertices. Assume the statement true up to $n$.

As $G$ is a tree, there exists $u\in V(G)$ with $d(u)=1$, i.e. $u$ is a leaf of $G$. Call $w$ the unique neighbour of $u$ in $G$.

As $G$ is connected ( it is a tree), then clearly $w$ has degree at least 2, and is a cut vertex for $G$, as it disconnect $u$ from $G$. Now for every other vertices, consider $G'=G\setminus\{u\}$. $G'$ is a graph on $n$ verices, hence we can apply the induction hypothesis : every vertex $v\neq w$ with degree at least 2 is a cut vertex for $G'$, hence a cut vertex for $G$.

Therefore every vertex of degree at least 2 in $G$ is a cut vertex