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.

Answer: T can be made directed, with some node x as root. If x is the center with neighbors a,b,c,d... and 2 of the subtrees rooted at this level contain leaves of max level k, then x is the unique center (replacing x by any of a,b,c.. would yield a tree of height k+1). If (only) x neighbor p has a leaf at level k in original tree (leaves on other subtrees are all at lower levels), then p could also be a center - some x neighbor q must then have a leaf at level k-1 in T rooted at x, which would now be at level k in tree rooted at p.

Alternate Answer: show that if x and y are both centers in T, then they must be adjacent.

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)?

Answer: there are 5**6 leaves L. By thm in text, 5**6 = (m-1)i + 1, so i = (5**6 -1)/4. The internal nodes send the letters, $2.50 for the 5.

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.

Answer: show that no narrowing can occur: k size s groups of men cannot be married just to women (k-1)*s women - which would be the case if there's an A of size k with range R(A) of size k-1

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.

Wives are ABC, husbands abc on near shore.

ab across, a returns: ABCac/b

ac across, a returns: ABCa/bc

BC across, Bb returns: ABab/Cc;

AB across, c returns: abc/ABC

ac across, c returns: bc/ABCa

then bc across

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: r5 - 2014-10-09 - 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