= Solution
For $n=1$ there are no <edges>. Every finite <tree> with at least two <vertices> has a <leaf of a graph>: an endpoint of a longest simple path cannot have another neighbor, since that would either create a cycle or extend the path. Delete that <leaf of a graph> and its sole <edge>. The remaining graph is still a <tree>, so <induction> gives $n-2$ remaining <edges> and $\boxed{n-1}$ original <edges>. Alternatively the decoding construction in (i) inserts exactly $n-2$ <edges> and then the final <edge>.
Back to article page
