You may collaborate on #2 and #6.

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

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)

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.

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.

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.

Due: February 28, in class

-- RobbieMoll - 25 Feb 2009

Topic revision: r4 - 2012-02-22 - 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