# CS 575/ Math 513 - Homework 2 Answers

• 1. vertices are labeled 0 – 16. Each vertex has arcs to next 3 (e.g. 8 -> 9, 10, 11). Second player wins by always getting to these states: 16,12,8, 4.
• 2. By pidgeonhole principle. N vertices can have at most degree n-1, but if it does, there can't be a vertex of degree 0. So only n-1 different degrees possible.
• 3. not isomorphic: cube has all even cycles, pinwheel has odd cycles.
• 4. a) LHS has 3 verts of degree 4; b) isomorphic
• 5. Number of vertices N must be odd, since number of odd vertices must be even. So in complete graph degree of each vertex is even. Thus if x has odd degree in G, x has odd degree in G-bar. So N-1.
• 6. LHS - yes; RHS- no: dkjic is an odd circuit
• 7. sure - but too hard to draw
• 8. First is impossible - reducible to (2 0 0 0 0); second can be reduced to (2 1 1 1 1), which is a real graph.
• 9. 11. K11 has 55 edges. K10 only has 45 edges, so it's not possible to get to 50 with just 10 vertices.

-- RobbieMoll - 2012-02-27
Topic revision: r2 - 2012-02-28 - 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