Quick Answers - Homework Assignment 5

1. Suppose a connected graph G has 20 edges. What is the maximum number of vertices possible in G?

Answer: 21 - this is the tree on 21 vertices

2. Let T be a (an undirected) tree. If the choice of x to be root yields a rooted tree of minimum height, then x is said to be a *center *of T. Show that any undirected tree has at most 2 centers.

3. Suppose that a chain letter is started by someone in the first week of the year. Each recipient of the chain letter mails copies on to five other people in the next week. After six weeks, how much money in total is spent on postage (figure 50¢ per letter)?

4. Construct trees with the following Prufer sequences: (4,5,6,2); (2,8,8,3,5,4)

Answer: easy drawing

5. Let T be an m-ary tree with n vertices, consisting of i internal nodes and L leaves. Suppose m is even. Show that n always has to be odd. Give two small examples for a fixed m that shows that i can be either even or odd.

Answer: since n = m*i + 1, m*i is even and thus n is odd.

6. Three jealous wives and their husbands come to a river. The party must cross a river in a boat that holds at most 2 people. Find a sequence of boat trips that will get the six people across the river without ever leaving any husband alone (without his wife) with another wife. Note: an unmarried husband/wife pairing is also not allowed for the boat crossing.

7. Suppose the degree sequence of a tree looks like this: (6,5,4,3,2,1….1). Determine how many 1’s there are in the sequence.

Answer: use these equations, assuming there are k 1's:

V = 5+k; V = E+1; 20+k = 2E (by handshaking lemma). So k = 12.

-- RobbieMoll - 2012-03-05

Topic revision: r2 - 2012-03-05 - RobbieMoll

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding UMass CS EdLab? Send feedback

Ideas, requests, problems regarding UMass CS EdLab? Send feedback