Given a graph $G=(V,E)$ that is a tree and $|V|\ge 2$, prove that $G$ has at least two vertices of degree $1$.
Asked
Active
Viewed 610 times
1 Answers
0
Hint: Try inducting on $|V|$. Base case is $|V| = 2$ which is very straightforward. For the inductive step, assume it holds for $|V| = n$ and try to show it for $|V| = n+1$. Use the fact that trees are acyclic, therefore deleting any edge of a tree will give you two connected components $G_1 = (V_1, E_1)$ and $G_2 = (V_2,E_2)$, both of which are trees, and note that $|V_1|, |V_2| \le n$, therefore...