Please could someone review the following proof that a tree with n nodes has n-1 edges?
I have seen versions which give base cases for both one node and two nodes, which I think are using strong induction. I have used simple induction - was this sufficient? Comments on the details and style of my proof in addition to any errors would be welcome.
Many thanks in advance.
To prove: Every tree of degree $n$ has $n-1$ edges, where n is a positive integer.
Let $p(n)$ be the proposition "a tree of degree n has n-1 edges."
We will use mathematical induction.
Base case: $p(1)$ is true since a tree with a single node has 0 edges.
Assume $p(k)$ for some positive integer $k$. We need to show $p(k+1)$ is true. Take a tree of degree $k$. Add a node. Since a tree must be connected this new node must be connected to the rest of the tree. This can only happen by means of a single edge, since in a tree multiple edges cannot exist between the same nodes, and connecting the new node to more than one other would create a cycle, which is also not permitted in a tree.
Thus $p(k+1)$ holds. By the principle of mathematical induction, we have shown that p(n) holds. ∎
For proving $p(k+1),$ you need to ensure that all trees of degree $k+1$ can be generated by your method "Take a tree of degree k. Add a node. " Once this is done your proof is right.
While this is easy, as after deleting a leaf, it's still a tree.