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

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

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

Ideas, requests, problems regarding UMass CS EdLab? Send feedback