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? 
Justify your  answer.

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
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 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

mersin escort adana escort izmir escort gaziantep escort