```Computer Science 575 / Mathematics 513
Combinatorics and Graph Theory
Midterm Exam
March 10, 2005

1.   (15) Characterize trees that have Euler trails.

2.    (15) An employees time clock shows that she worked 81 hours over a period of 10 days.
Show that on some pair of consecutive days the employee worked at least 17 hours. (note: employees work only whole hours.)

3.   (15)  Suppose the average degree of the vertices in a connected graph is 2. How many circuits does the graph have?

4.   (15) Suppose the degree sequence of a tree looks like this: (5,4,3,2,1.1).
Determine how many 1s there are in the sequence.

5.   (10) Show from first principles that a graph on 5 vertices, all of degree at least 3, must have a Hamiltonian circuit.

6.   (15) Suppose a graph has 6 vertices, all of degree 4.
Prove that such a graph cannot be planar, or show that it can be, by giving a planar depiction of such a graph.

7.   (15 points)

(a) Prove that every planar graph has a vertex of degree <= 5.

(b)   Then prove by induction that every planar graph can be colored with 5 colors.

```

-- RobbieMoll - 04 Mar 2004

Topic revision: r2 - 2006-10-06 - 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