8.2 How to Grow Trees 143v. The other neighbors ofvare called thesonsofv. The rootrdoes not
have a father, but all its neighbors are called its sons.
We now make a basic genealogical assertion:Every node is the father of
its sons. Indeed, letvbe any node, and letube one of its sons. Consider
the unique pathPconnectingvtor. The nodeucannot lie onP: It cannot
be the first node afterv, since then it would be the father ofv, and not its
son; and it cannot be a later node, since then in going fromvtouon the
pathPand then back tovon the edgeuvwe would traverse a cycle. But
this implies that in adding the nodeuand the edgeuvtoPwe get a path
connectingutor. Sincevis the first node on this path afteru, it follows
thatvis the father ofu. (Is this argument valid whenv=r? Check!)
We have seen that every node different from the root has exactly one
father. A node can have any number of sons, including zero. A node with
no sons is called aleaf. In other words, a leaf is a node with degree 1,
different fromr.
8.1.1Prove part (b) of Theorem 8.1.1.8.1.2Prove that connecting two nodesuandvin a graphGby a new edge
creates a new cycle if and only ifuandvare in the same connected component
ofG.
8.1.3Prove that in a tree, every two nodes can be connected by auniquepath.
Conversely, prove that if a graphGhas the property that every two nodes can be
connected by a path, and there is only one connecting path for each pair, then
the graph is a tree.
8.2 How to Grow Trees.......................
The following is one of the most important properties of trees.
Theorem 8.2.1Every tree with at least two nodes has at least two nodes
of degree 1.
Proof. LetGbe a tree with at least two nodes. We prove thatGhas a
node of degree 1, and leave it to the reader as an exercise to prove that it
has at least one more. (A path has only two such nodes, so this is the best
possible we can claim.)
Let us start from any nodev 0 of the tree and take a walk (climb?) on the
tree. Let’s say we never want to turn back from a node on the edge through
which we entered it; this is possible unless we get to a node of degree 1, in
which case we stop and the proof is finished.
So let’s argue that this must happen sooner or later. If not, then even-
tually we must return to a node we have already visited; but then the