8.2 How to Grow Trees 145By the induction hypothesis, every tree with fewer nodes thanGarises
by the construction; in particular,G′does. But thenGarises fromG′by
one more iteration of the second step. This completes the proof of Theorem
8.2.2.
Figure 8.2 shows how trees with up to 4 nodes arise by this construction.
Note that there is a “tree of trees” here. The fact that the logical structure
of this construction is a tree does not have anything to do with the fact
that we are constructing trees: any iterative construction with free choices
at each step results in a similar “descent tree”.
FIGURE 8.2. The descent tree of treesThe Tree-growing Procedure can be used to establish a number of prop-
erties of trees. Perhaps most important of these concerns the number of
edges. How many edges does a tree have? Of course, this depends on the
number of nodes; but surprisingly, it dependsonlyon the number of nodes:
Theorem 8.2.3Every tree onnnodes hasn− 1 edges.
Proof. Indeed, we start with one more node (1) than edge (0), and at
each step, one new node and one new edge are added, so this difference of
1 is maintained.
8.2.2LetGbe a tree, which we consider as the network of roads in a medieval
country, with castles as nodes. The king lives at noder. On a certain day, the
lord of each castle sets out to visit the king. Argue carefully that soon after they
have left their castles, there will be exactly one lord on each edge. Give a proof
of Theorem 8.2.3 based on this.