# A Sample Midterm

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

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