Computer Science 575 / Mathematics 513

Combinatorics and Graph Theory

Midterm Exam

October 19, 2006

(closed book, 75 minutes, in class)

1. (16) Suppose a tree has vertices of degree 5 and degree 1 only. If there

are (4n+2) vertices altogether, how many are there of degree 5?

2. (16) An undirected graph G is self-complementary if it is isomorphic

to its complement, GC . Consider graphs with 3, 4 and 5 vertices. In each

case, find a self-complementary graph of that size, or prove that one can't

exist.

3. (16) Can there be a disconnected graph with this degree sequence:

(4,4,3,3,3,3,3,3)? Either draw such graph, or show that one can't exist.

4. (20) Prove that in any graph G, either G or its complement, GC, is

connected.

5. (16) Ten people are at a party, with (integer) ages that range from 0 to

100. Show that there are two distinct subsets of people at this party, A

and B, such that the sum of the ages of the people in group A equals the

sum of the ages of the people in group B.

6. (16) The wheel graph, Wn (see W5, below), has n+1 vertices. It's

clearly planar. As a function of n, how many edges can be added to Wn

in such a way as to maintain planarity? For example, W3 is 0. In the case

of W4, exactly 1 edge can be added without destroying graph planarity.

In your answer, show some examples, but also give an expression in n

that tells how many can be added, and justify the expression you give.

-- RobbieMoll - 20 Feb 2009

Edit | Attach | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r1 - 2009-02-20 - 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