Brief Answers 1. 2.1 - 2 (a) - any odd n; (b) K2 (c) both r,s even 2. 2.1 - 4 lift twice - 6 odd degree vertices. connect 2 of them, then lift (1); then connect 2 more, then lift (2); then connect the last two. 3. 2.1 - 10 Not possible: cells on board are vertices, edges to those other cells where a knight can move. More than 2 have odd degree. 4. 2.1 - 16 If all vertices have even degree, then each line in the line graph has even degree. K4 has no Euler cycle, but its line graph does. 5. 2.2 - 4 (d,e) d can’t work; nor can e. 6. 2.2 - 16 looking for a directed HAM circuit in the graph where seat positions are nodes. Circuit has 25 vertices – so either north / south or east / west pairs has a different count, and thus you can’t return to start. 7. 2.3 - 6 a) 3-color the triangles, starting at a. Then the a-f arc should create no problems. This is equitable. 1-c is obviously 2-colorable and equitable 8. 2.3 - 10 a-draw the n+1st circle. Inside it’s internally consistent and properly colored, by induction, but it’s wrong at every boundary. Flip all colors inside this new circle. B- use color A for all regions with even overlap, color B for odd overlap. Must have different colors at every boundary, since each boundary changes by 1 the overlap count. 9. 2.3 - 12 verts = animals; edges = animals that can’t get along; a color = open space (animals in that open space get same color). 10. 2.4 - 2 Must be 7 regions. If all are bounded by 4 or more edges, then since 2E = region degree sum, there must be 14 edges. But there are only 13, so there must be a triangle, and thus a 3-cycle. 11. 2.4 - 6 a. color classes are independent sets, and they cover the graph; b. If min degree is d, then no independent set can contain more than n-d vertices. 12. 2.4 - 14 Do the standard proof, by induction: color every vertex but the deg 4 vertex using 4 colors, then color that last vertex using the argument in the book (the big blob lemma).

-- RobbieMoll - 05 Oct 2006

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

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