Prove that any tree with n nodes has n $1$ edges. Hint: to get a smaller subproblem, remove a leaf node, i$.$e$.$ a degree $1$ node, from the tree. To prove that any tree has a leaf node, note that trees do not have cycles and consider a path that starts at the root node.