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 
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