Properties Of Trees

Properties of Trees: We will often need results relating the numbers of edges and vertices of various types in trees.

THEOREM 2 A tree with n vertices has n − 1 edges.

Proof:We will use mathematical induction to prove this theorem. Note that for all the trees here we can choose a root and consider the tree rooted.

BASIS STEP: When n = 1, a tree with n = 1 vertex has no edges. It follows that the theorem is true for n = 1.

INDUCTIVE STEP: The inductive hypothesis states that every tree with k vertices has k − 1 edges, where k is a positive integer. Suppose that a tree T has k 1 vertices and that v is a leaf of T (which must exist because the tree is finite), and let w be the parent of v. Removing from T the vertex v and the edge connecting w to v produces a tree T' with k vertices, because the resulting graph is still connected and has no simple circuits. By the inductive hypothesis, T' has k − 1 edges. It follows that T has k edges because it has one more edge than T' , the edge connecting v and w. This completes the inductive step.

Recall that a tree is a connected undirected graph with no simple circuits. So, when G is an undirected graph with n vertices, Theorem 2 tells us that the two conditions (i) G is connected and (ii) G has no simple circuits, imply (iii) G has n − 1 edges. Also, when (i) and (iii) hold, then (ii) must also hold, and when (ii) and (iii) hold, (i) must also hold. That is, ifGis connected and G has n − 1 edges, then G has no simple circuits, so that G is a tree (see Exercise 15(a)), and if G has no simple circuits and G has n − 1 edges, then G is connected, and so is a tree. Consequently, when two of (i), (ii), and (iii) hold, the third condition must also hold, and G must be a tree.

COUNTINGVERTICES IN FULL m-ARY TREES The number of vertices in a full m-ary tree with a specified number of internal vertices is determined, as Theorem 3 shows. As in Theorem 2, we will use n to denote the number of vertices in a tree.

THEOREM 3 A full m-ary tree with i internal vertices contains n = mi 1 vertices.
Proof: Every vertex, except the root, is the child of an internal vertex. Because each of the i internal vertices has m children, there are mi vertices in the tree other than the root. Therefore, the tree contains n = mi 1 vertices.

Suppose that T is a full m-ary tree. Let i be the number of internal vertices and l the number of leaves in this tree. Once one of n, i, and l is known, the other two quantities are determined. Theorem 4 explains how to find the other two quantities from the one that is known.

THEOREM 4 A full m-ary tree with
(i ) n vertices has i = (n − 1)/m internal vertices and l = [(m − 1)n 1]/m leaves,
(ii ) i internal vertices has n = mi 1 vertices and l = (m − 1)i 1 leaves,
(iii ) l leaves has n = (ml − 1)/(m − 1) vertices and i = (l − 1)/(m − 1) internal vertices.
Proof: Let n represent the number of vertices, i the number of internal vertices, and l the number of leaves. The three parts of the theorem can all be proved using the equality given in Theorem 3, that is, n = mi 1, together with the equality n = l i, which is true because each vertex is either a leaf or an internal vertex. We will prove part (i) here. The proofs of parts (ii) and (iii) are left as exercises for the reader. Solving for i in n = mi 1 gives i = (n − 1)/m. Then inserting this expression for i into the equation n = l i shows that l = n − i = n − (n − 1)/m = [(m − 1)n 1]/m. Example 9 illustrates how Theorem 4 can be used.

EXAMPLE 9 Suppose that someone starts a chain letter. Each person who receives the letter is asked to send it on to four other people. Some people do this, but others do not send any letters. How many people have seen the letter, including the first person, if no one receives more than one letter and if the chain letter ends after there have been 100 people who read it but did not send it out? How many people sent out the letter?

Solution: The chain letter can be represented using a 4-ary tree. The internal vertices correspond to people who sent out the letter, and the leaves correspond to people who did not send it out. Because 100 people did not send out the letter, the number of leaves in this rooted tree is l = 100. Hence, part (iii) of Theorem 4 shows that the number of people who have seen the letter is n = (4 · 100 − 1)/(4 − 1) = 133. Also, the number of internal vertices is 133 − 100 = 33, so 33 people sent out the letter.

BALANCED m-ARY TREES It is often desirable to use rooted trees that are “balanced” so that the subtrees at each vertex contain paths of approximately the same length. Some definitions will make this concept clear. The level of a vertex v in a rooted tree is the length of the unique path from the root to this vertex. The level of the root is defined to be zero. The height of a rooted tree is the maximum of the levels of vertices. In other words, the height of a rooted tree is the length of the longest path from the root to any vertex.

EXAMPLE 10 Find the level of each vertex in the rooted tree shown in Figure 13. What is the height of this tree?
Solution: The root a is at level 0. Vertices b, j , and k are at level 1. Vertices c, e, f , and l are at level 2.Vertices d, g, i, m, and n are at level 3. Finally, vertex h is at level 4. Because the largest level of any vertex is 4, this tree has height 4.

A rooted m-ary tree of height h is balanced if all leaves are at levels h or h − 1.

EXAMPLE 11 Which of the rooted trees shown in Figure 14 are balanced?
Solution: T1 is balanced, because all its leaves are at levels 3 and 4. However, T2 is not balanced, because it has leaves at levels 2, 3, and 4. Finally, T3 is balanced, because all its leaves are at level 3.