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. There are r*s couples at a dance. The men are divided into r groups, by age, with s guys in each group; the women are also divided into r groups, by height, with s women in each group. Show that r couples can be selected such that every height group and every age group is represented.

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. 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.

Due: Tuesday October 7, in class

-- RobbieMoll - 25 Feb 2009

Topic revision: r6 - 2014-09-30 - 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