I wonder if you guys can help me find an easier solution for this.
Show that for every n >= 3 a tree exists with exactly n nodes and n - 1 leaves.
My instructor had a solution that basically covered induction, constructing a new tree with a new node and edge, then counting its degrees and pove that the new tree is as acyclic and connected as the previous. I found this solution very extensive and was wondering whether there is a quicker and more efficient way.
So if there is one and you know it, maybe you can share...? ^^
Given $n$ nodes $v_0,\ldots, v_{n-1}$, let there be an edge $v_0v_i$ for $1\le i\le n-1$. Then $v_0$ has degree $n-1>1$, all other $v_i$ have degree $1$, the graph is connected (e.g. $v_i\to v_0\to v_j$) and acyclic (because only one node has degree $>1$).