Homework four quick answers

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 

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

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