Properties of trees
Theorem 2. A tree with n vertices has n-1 edges.
Proof. Choose a vertex r as the root. There is 1-to-1 correspondence
between edges and vertices other than the root. In particular, the edge
(u,v) corresponds to v. To see that this correspondence is 1-to-1, observe
that every node (except the root) has exactly one parent.
So, there are as many non-root vertices as edges.
If n is the total number of vertices, n-1 then would be the number of
non-root vertices and hence the number of of edges. End of proof.
Theorem 3. A full m-ary tree with i internal vertices contains mi+1
Proof. Each of the i internal vertices has m children, so the total
number of (somebody’s) children in the tree is mi. But every vertex,
except the root, is somebody’s child. So, together with the root, the
total number of vertices is mi+1. End of proof.