CS 575/ Math 513 - Homework 2 Answers

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