Exercises 1. Which of these graphs are trees? MM VA oh] | 1 | kK a) Ld] 2, Which of these graphs are trees? a) x , PK an e +1 a) Which vertex is the root? 1b) Which vertices are internal? ©) Which vertices are leaves? d) Which vertices are children of j? ) Which vertex is the parent of h? £) Which vertices are siblings of 0? 1g) Which vertices are ancestors of m’ 1h) Which vertices are descendants of 6? 4. Answer the same questions as listed in Exercise 3 for the rooted tree illustrated. 5, Is the rooted tree in Exercise 3 a full m-ary wee for some positive imeger m? 6. Is the rooted tree in Exercise 4 a full m-ary tee for some positive integer m? 7. What is the level of each vertex of the rooted tree in Ex- excise 3? 8. What is the level of each vertex of the rooted tree in Ex- ercise 4? 9. Draw the subtree ofthe tree in Exercise 3 that is rooted at ada. bye oe 10, Draw the subtree of the tree in Exercise 4 that is rooted at a) a. bye. oe 11, a) How many nonisomorphic unrooted trees are there with three vertices? b) How many nonisomorphic rooted trees are there with three vertices (using isomorphism for directed graphs)? 8) How many nonisomorphic unrooted trees are there with four vertices? 1b) How many nonisomorphic rooted trees are there with four vertices (using isomorphism for directed graphs)?"13. a) How many nonisomorphic unrooted trees are there with five vertices? 'b) How many nonisomorphic rooted trees are there with five vertices (using isomorphism for directed graphs)?” Show that a simple graph is a tree if and only if it is connected but the deletion of any of its edges produces a ‘graph that is not connected Let G be a simple graph with n vertices. Show that 8) G isa tree if and only if itis connected and has n edges. b) G isa tree if and only if G has no simple circuits and has n — 1 edges. (Hint: To show that G is connected. if ithas no simple circuits and n ~ 1 edges, show that G cannot have more than one connected component. 16. Which complete bipartite graphs Kmn. where m and n are positive integers, are trees? 17, How many edges does a tree with 10,000 vertices have? 18, How many vertices does a full S-ary tree with 100internal vertices have? 19, How many edges does a full binary tree with 1000 internal vertices have? 20. How many leaves does a full 3-ary tree with 100 vertices have? 21, Suppose 1000 people enter a chess tournament. Use a rooted tree model of the tournament to determine how ‘many games must be played to determine a champion, if a player is eliminated after one loss and games are played until only one entrant has not lost (Assume there are no ties.) 22. A chain letter starts when a person sends a leter to five others. Bach person who receives the letter either sends it to five other people who have never received it or does not send it to anyone. Suppose that 10,000 people send out the letter before the chain ends and that no one receives ‘more than one letter. How many people receive the letter, and how many do not send it out? 23, A chain letter starts with a person sending a letter out to 10 others. Each person is asked to send the letter out to 10 others, and each letter contains a list ofthe previous six people in the chain. Unless there are fewer than six names in the list, each person sends one dollar tothe first person in this list, removes the name of this person from the list, moves up each of the other five names one posi- tion, and inserts his or her name at the end of this list. If no person breaks the chain and no one receives more than fone letter, how much money will a person in the chain ultimately receive? Either draw a full m-ary tree with 76 leaves and height 3, ‘where m is a positive integer, or show that no such tree exists #25, Either draw a full m-ary tree with 84 leaves and height 3, ‘where m is a positive integer, or show that no such tree exists 924, **26, A full m-ary tree T has 81 leaves and height 4. ‘8) Give the upper and lower bounds for m. bb) What is m if 7 is also balanced? A complete m-ary tree isa full m-ary tree in which every leaf is at the same level. 27. Construct a complete binary tree of height 4 and a com- plete 3-ary tree of height 3. 28, How many vertices and how many leaves does acomplete -meary tree of height h have? 29, Prove ‘a) part (ii) of Theorem 4 b) part (ii) of Theorem 4. *30. Show that a full m-ary balanced tree of height fk has more than m=! leaves. 31. How many edges are there in a forest ofr trees containing, a total of n vertices? 32, Explain how a tree can be used to represent the table of contents of a book organized into chapters, where each chapter is organized into sections, and each section is or- ‘ganized into subsections. 33. How many different isomers do these saturated hydro- ‘carbons have? a) Gs b) Csth ©) Collis 34, What does each of these represent in an organizational twee? 4a) the parent of a vertex b) a child ofa vertex ©) asibling ofa vertex 4) the ancestors ofa vertex ©) the descendants of a vertex 1) the level ofa vertex f) the height of the ree 38. Answer the same questions as those given in Exercise 34 fora rooted tree representing a computer file system. 36, a) Draw the complete binary tree with 15 vertices that represents atree-connected network of 15 processors. ) Show how 16 numbers can be added using the 15 pro- ccessors in part (a) using four steps. 37, Let n be a power of 2. Show that n numbers can be added in log steps using a tree-connected network of m — 1 processors. 38, A labeled tree is a tree where each vertex is assigned a label. Two labeled trees are considered isomorphic when there isan isomorphism between them that preserves the labels of vertices. How many nonisomorphic trees are there with three vertices labeled with different integers from the set (1,2, 3}? How many nonisomorphic trees are there with four vertices labeled with different inte- ‘gers from the set (1.2. 3,4)?‘The eccentricity of a vertex in an unrooted tree is the length of the longest simple path beginning at this vertex. A vertex is called a center if no vertex in the tree has smaller eccentricity than this vertex. In Exercises 39-41 find every vertex that is a center in the given tree. *46. How many vertices, leaves, and internal v 11.2 Applications of Trees 757 42, Show that acenter should be chosen asthe root to produce a rooted tree of minimal height from an unrooted tree. #43, Show that a tree has either one center or two centers that are adjacent. 44, Show that every tree can be colored using two colors. The rooted Fibonacci trees Ty are defined recursively in the following way. 1 and 7> are both the rooted tree consisting of asingle vertex, and for m = 3,4... the rooted tree Ty is, ‘constructed from a root with T—1 as its left subtree and T—2 as its right subiree. 45, Draw the first seven rooted Fibonacci trees. 8 does the rooted Fibonacci tree Ty have, where mis a positive inte- ‘ger? What is its height? 47, What is wrong with the following “proof” using mathe- ‘matical induction of the statement that every tree with vertices has a path of length n — 1, Basis step: Every tree with one vertex clearly has a path of length 0. inductive step: Assume that a tree with n vertices has a path of length n — 1, which has w as its terminal vertex, Add a vertex v and the edge from 1 to v. The resulting tree has n+ | vertices and has a path of length 1. This completes the inductive step. {55'#48, Show that the average depth of a leaf in a binary tree with n vertices is 8 (log m).CHAPTER 11 Trees SECTION 11.1 Introduction to Trees 5. These exercises give the reader experience working with tree terminology, and in particular with the relation- ships between the height and the numbers of vertices, leaves, and internal vertices of a tree. Exercise 13 should be done to get a fecling for the structure of trees. One good way to organize your enumeration of trees (such as all nonisomorphie trees with five vertices) is to focus on a particular parameter, such as the length of a Iongest path in the tree. This makes it easier to include all the trees and not count any of them twice. Review the theorems in this section before working the exercises involving the relationships between the height and the numbers of vertices, leaves, and internal vertices of a tree. For a challenge that gives a good feeling for the flavor of arguments in graph theory, the reader should try Exercise 43. In many ways trees are recursive creatures, and Exercises 45 and 46 are worth looking at in this regard. . a) This graph is connected and has no simple circuits, so it is a tree. b) This graph is not connected, so it is not a tree. ¢) This graph is connected and has no simple circuits, 50 it is a tree. d) This graph has a simple circuit, so it is not a tree, €) This graph is connected and has no simple circuits, so it is a treo. ) This graph has a simple circuit, so it is not a tree. a) Vertex a is the root, since it is drawn at the top. b) The internal vertices are the vertices with children, namely a, b,c, d, f, A. J, q, and t c) The teaves are the vertices without children, namely €, g, i, k, 1, m,n, 0, p, 1, 8, and u 4d) The children of j are the vertices adjacent to j and below j, namely q and r e) The parent of h is the vertex adjacent to h and above h, namely c. f) Vertex o has only one sibling, namely p, which is the other child of o's parent. h. 8) The ancestors of m are all the vertices on the unique simple path from m back to the root, namely f, 6, and a. h) The descendants of b are all the vertices that have b as an ancestor, namely ¢, f, l,m, and n. This is not a full m-ary tree for any m. It is an m-ary tree for all m > 3, since each vertex has at most 3 children, but since some vertices have 3 children, while others have 1 or 2, it is not full for any m. ‘We can easily determine the levels from the drawing. The root a is at level 0. The vertices in the row below @ are at level 1, namely &, ¢, and d. The vertices below that, namely € through & (in alphabetical order), are at level 2. Similarly ¢ through 7 are at level 3, 3 and ¢ are at level 4, and w is at level 5, We describe the answers, rather than actually drawing pictures. a) The subiree rooted at a is the entire tree, since a is the root. b) The subtree rooted at ¢ consists of five vertices—the root ¢, children g and h of this root, and grandchildren © and p—and the four edges eg, ch, ho, and hp ¢) The subtree rooted at ¢ is just the vertex e.404 4. 13. 15. Chapter 11° Trees We find the answer by carefully enumerating these trees, ie., drawing a full set of nonisomorphic trees. One ‘way to orgenizo this work 60 as to avoid leaving any trees out or counting the same tree (up to isomorphism) ‘more than once is to list the trees by the length of their longest simple path (or longest simple path from the root in the case of rooted trees). a) There is only one tree with three vertices, namely Ky,2 (which can also be thought of as the simple path of length 2). b) With three vertices, the longest path from the root can have length 1 or 2. There is only one tree of each type, so there are exactly two nonisomorphic rooted trees with 3 vertices, as shown below. | N We find the answer by carefully enumerating these trees, ie., drawing o full set of nonisomorphic trees. One ‘way to organize this work 0 as to avoid leaving any trees out or counting the same tree (up to isomorphism) more than once is to list the trees by the length of their longest simple path (or longest simple path from the root in the case of rooted trees). a) If the longest simple path has length 4, then the entire tree is just this path. If the longest simple path has length 3, then the fifth vertex must be attached to one of the middle vertices of this path. If the longest simple path has length 2, then the tree is just K;,4. Thus there are only three trees with five vertices. They can be pictured as the first, second, and fourth pictures in the top row below. 'b) For rooted trees of length 5, the longest path from the root can have length 1, 2, 3 or 4. ‘There is only one tree with longest path of length 1 (the other four vertices are at level 1), and only one with longest path of length 4. If the longest path has length 3, then the fifth vertex (after using four vertices to draw this path) can be “attached” to either the root or the vertex at level 1 or the vertex at level 2, giving us three nonisomorphic trees. If the longest path has length 2, then there are several possibilities for where the fourth and fifth vertices can be “attached.” ‘They can both be adjacent to the root; they can both be adjacent to the vertex at level 1; one can be adjacent to the root and the other to the vertex at level 1; or one can be adjacent to the root and the other to this vertex: in all there are four possibilities in this case. Thus there are 2 total of nine nonisomorphiic rooted trees on 5 vertices, as shown below. aT PRL &é AR A a) We will prove this statement using mathematical induction on n, the number of vertices of G. (This exercise can also be done by using Exereise 14 and Theorem 2. Such a proof is given in the answer section of the textbook.) If n = 1, then there is only one possibility for G, it is a tree, it is connected, and it has 1—1=0 edges. ‘Thus the statement is true. Now let us assume that the statement is true for simple graphs with n vertices, and let G be a simple graph with m +1 vertices. ‘There are two things to prove here. First let us suppose that G is a tree; we must show that G is connected and has (n +1) —1=n edges. Of course G is connected by definition. In order to prove that GSection 11.1 Introduction to Trees 405 has the required number of edges, we need the following fact: a tree with at least one edge must contain a vortex of degree 1. (To see that this is 60, let P be a simple path of greatest possible length; since the tree has no simple citcuits, such a maximum length simple path exists. The ends of this path must be vertices of degree 1, since otherwise the simple path could be extended.) Let v be a vertex of degree I in G, and let G" be G with v and its incident edge removed. Now G’ is still a tree: it has no simple circuits (since G had none) and itis still connected (the removed edge is clearly not needed to form paths between vertices different from v). ‘Therefore by the inductive hypothesis, G’, which has n. vertices, has n—1 edges; it follows that G, which has one more edge than G’, has n edges. Conversely, suppose that G is connected and has n edges. If G is not a tree, then it must contain a simple circuit. If we remove one edge from this simple circuit, then the resulting graph (call it G’) is still connected. If Gi is a tree then we stop; otherwise we repeat this process. Since G had only finitely many edges to begin with, this process must eventually terminate at some tree T with n-+1 vertices (T has all the vertices that @ had). By the paragraph above, T therefore has n edges. But this contradicts the fact that we removed at least one edge of @ in order to construct T. Therefore our assumption that @ was not a tree is wrong, and our proof is complete. bb) For the “only if" direction, suppose that G is a tree. By part (a), G has n—1 edges, and by definition, hhas no simple circuits. For the “if” direction, suppose that Chas uo simple circuits and has ”—1 edges. The only thing left to prove is that G is connected. Let ¢ equal the number of components of G, each of whieh is necessarily a tree, say with n, vertices, where S°°_,n, =n. By part (a), the total mumber of edges in G is S_,(r4 1) = nc. Since we are given that this equals n— 1, it follows that = 1, ie., G is connected. 17. Since a tree with n vertices has n—1 edges, the answer is 9999. 19, Each internal vertex has exactly 2 edges leading from it to its children. Therefore we can count the edges by multiplying the number of internal vertices by 2. Thus there are 2- 1000 = 2000 edges. 21. We can model the tournament as a full binary tree. Each internal vertex represents the winner of the game played by its two children, There are 1000 leaves, one for each contestant. The root is the winner of the entire tournament. By Theorem 4(ii), with m= 2 and ! = 1000, we see that i = (I - 1)/(m 1) = 999. Thus exactly 999 games must be played to determine the champion. 23, Let P be a person sending out the letter, Then 10 people receive a letter with P's name at the bottom of the list (in the sixth position). Later 100 people receive a letter with P's name in the fifth position. Similarly, 1000 people receive a letter with P’s name in the fourth position, and so on, until 1,000,000 people receive the letter with P's name in the first position. Therefore P should receive $1,000,000. ‘The model here is a full 10-ary tree. 25. No such tree exists. Suppose it did. By Theorem 4(si), we know that a tree with these parameters must have 4 = 83/(m — 1) internal vertices. In order for this to be a whole number, m—1 must be a divisor of 83. Since 83 is prime, this means that m = 2 or m= 84. If m= 2, then we can have at most 15 vertices in all (the root, two at level 1, four at level 2, and eight at level 3). Som cannot be 2. If m= 84, then i= 1, which tells us that the root is the only internal vertex, and hence the height is only 1, rather than the desired 3. ‘These contradictions tell us thet no tree with 84 leaves and height 3 exists, 27, The complete binary tree of height 4 has 5 rows of vertices (levels 0 through 4), with each vertex not in the bottom row having two children. The complete S-ary tree of height 3 has 4 rows of vertices (levels 0 through 3), with each vertex not in the bottom row having three children.406 Chapter 11 Trees 29, For both parts we use algebra on the equations n = i+! (which is true by definition) and n= mi+1 (which is proved in Theorem 3). a) That n= mi +1 is one of the given equations. For the second equality here, we have | = n— (mi +1)-i=(m-1)i+1. b) If we subtract tho two given equations, then we obtain 0 = (1—m)i+(L-1), or (m—1)i = 1-1. It follows that: #= ((=1)/(m—1). Then n= é41 = [= 1)/(m—1)] +1 = (1-1 41m —D/ (n= 1) = (m= 1)/(m=1). 31, In each of the t trees, there is one fewer edge than there are vertices. Therefore altogether there are t fewer edges than vertices. Thus there are n— t edges. 33. The number of isomers is the number of nonisomorphic trees with the given numbers of atoms. Since the hydrogen atoms play no role in determining the structure (they simply are attached to each carbon atom in sufficient number to make the degree of each carbon atom exactly 4), we need only look at the trees formed by the carbon atoms, In drawing our answers, we will show the tree of carbon atoms in heavy lines, with the hydrogen atom attachments in thinner lines. a) There is only one tree with three vertices (up to isomorphism), the path of length 2. Thus the answer is 1. The heavy lines in this diagram of the molecule form this tree. tH b) There are 3 nonisomorphic trees with 5 vertices: the path of length 4, the “star” K1,«, and the tree that consists of a path of length 3 together with one more vertex attached to one of the middle vertices in the path, Thus the answer is 3. Again the heavy lines in the diagrams of the molecules form these trees HY TE ¢) We need to find all the nonisomorphic trees with 6 vertices, except that we must not count the (one) tree with a vertex of degree 5 (since each carbon can only be attached to four other atoms). The complete set of trees is shown below (the heavy lines in these diagrams). ‘Thus the answer is 5.Section 11.1 Introduction to Trees 407 ‘85. a) The parent of a vertex v is the directory in which the file or directory represented by v is contained. 'b) The child of a vertex v (and v must represent a directory) is a file or directory contained in the directory that v represents. c) If u and v are siblings, then the files or directories that u and v represent are in the same directory. ) The ancestors of vertex v are all directories in the path from the root directory to the file or directory represented by v. e) The descendants of a vertex v are all the files and directories either contained in v, or contained in directories contained in v, ete. £) The level of a vertex » tells how far from the root directory is the file or directory represented by v. g) The height of the tree is the greatest depth (i.c., level) at which a file or directory is buried in the system. 87. Suppose that n = 2*, where k is a positive integer. We want to show how to add n numbers in logn steps uusing a tree-connected network of n — 1 processors (recall that logn means logy). Let us prove this by ‘mathematical induction on k. If k = 1 there is nothing to prove, since then n = 2 and n—1= 1, and certainly in log2 = 1 step we can add 2 numbers with I processor. Assume the inductive hypothesis, that wwe can add n=2* numbers in logn steps using a tree-connected network of n 1 processors. Suppose now that we have 2n = 2+! numbers to add, 2, t2,..., Z2n- The tree-connected network of 2n— 1 processors consists of the tree-connected network of n — 1 processors together with two new processors as children of each leaf in the (n~ 1)-processor network. In one step we can use the leaves of the larger network to add ‘© +2, 23+ 24,..-, Zan-1 + Lan. This gives us m numbers. By the inductive hypothesis we can now use the rest of the network to add these numbers using logn steps. In all, then, we used 1 + (logn) steps, and, just as desired, log(2n) = log 2+ logn = 1 +logn. This completes the proof. 39. We need to compute the eccentricity of each vertex in order to find the center or centers. In practice, this does not involve much computation, since we can tell at a glance when the eccentricity is large. Intuitively, the center oF centers are near the “middle” of the tree. The eccentricity of vertex ¢ is 3, and it is the only vertex with eccentricity this small. Indeed, vertices @ and 6 have eccentricities 4 and 5 (look at the paths to 1); vertices d, f, 9, j, and k all have eccentricities at least 4 (again look at the paths to 1); and vertices e, A, i, and 1 also all have eccentricities at least 4 (look at the paths to k). Therefore ¢ is the only center. 41. See the comments for the solution to Exercise 39. The eccentricity of vertices c and A are both 3. The ‘eccentricities of the other vertices are all at least 4. Therefore c and h are the centers. 43. Certainly a tree has at least one center, since the set of eccentricities has a minimum value. First we prove that if u and v are any two distinct centers (say with minimum eccentricity ), then u and v are adjacent. Let P be the unique simple path from u to v. We will show that P is just u,v. If not, let c be any other vertex on P, Since the eccentricity of c is at least ¢, there is a vertex w such that the unique simple path Q from c to w has length at lonst e. This path Q may follow P for awhile, but once it diverges from P it cannot rejoin P without there being a simple circuit in the tree. In any case, @ cannot follow P towards408 Chapter 11 Trees both w and v, so suppose without loss of generality that it does not follow P towards u. Then the path from 1 to c and then on to w is simple and of length greater than e, a contradiction. Thus no such c exists, and wand v are adjacent. Finally, to see that there can be no more than two centers, note that we have just proved that every two centers are adjacent. If there were three (or more) centers, then we would have a Ks contained in the tree, contradicting the definition thot a tree has no simple circuits, 45. We follow the recursive definition and produce the following pictures for Ts through 7; (of course Ty and T are both the tree with just one vertex). For example, Ts has T (a single vertex) as its left subtree and Ty (again a single vertex) as its right subtree. uy 47, This “proof” shows that there exists a tree with m vertices having a path of length n—1. Note that the inductive step correctly takes the tree whose existence is guaranteed by the inductive hypothesis and correctly constructs a tree of the desired type. However, the statement was that every tree with n vertices has a path of length 7 — 1, and this was not shown. A proof of the inductive step would need to start with an arbitrary tree with n +1 vertices and show that it had the required path. Of course no such proof is possible, since the statement is not true. Douglas West, whose Introduction to Graph Theory is an excellent book on that subject, calls this mistake the induction trap.