# CS 575 / Math 513 - Homework 4 Quick Answers

1. a) Kn for odd n; b) K2; c) r,s both even.

2. No - this would be an Euler cycle on the graph of board cells, with 2 cells linked if a knight can move between them. Quite a few (close to corners) have odd degree.

3. a) If G has an Euler cycle, then each vertex has even degree; therefore in L(G) each edge has an odd count of adjacencies on both ends, and thus even degree. However K4-{one diagonal edge} has 2 odd degree vertices, while its line graph has all even degree vertices.

4. Straightforward identification / construction

5. Form a fan: vertex a connected to vertices b,c,d. That leaves vertices e,f unaccounted for. There are two cases: they are connected to each other; and they aren't, so each is connected to all of b,c,d. These two cases are easy to handle.

6. The "cells" in the 5x5 array are vertices in the classroom graph, and they have "checkerboard" coloring (based on the shift pattern of the kids). So the graph is 2 colorable, and thus all circuits must have even length. But since there are 25 vertices and everyone must move in a non-trivial circuit, some circuit would have to be odd for the shift to be possible.

7. From definition - an Euler cycle visits every edge exactly once, returning to starting edge. So this is a HAM in L(G).

8. Color a region red if it is made by an odd number of overlapping circles, blue if even number of overlaps. Then adjacent regions across a circle boundary will have different overlap parity, and hence colors.

9. Every planar bipartite graph must satisfy E <= 2V-4.

10. Argue that every circuit must have even length. To do this, first show that if two circuits of even length enclose two regions, and if those two circuits have common edges, then the circuit that encloses the two regions has even length. Extend this to any number of even length region-enclosing circuits.

-- RobbieMoll - 2012-02-28

Topic revision: r3 - 2012-02-29 - 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