Past exam of the Probability, statistics and options II course of the University of Oxford / 2010 / R / R2 / iv

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.