(c) True or False: Let G be a graph and let G7  C G be a subgraph of G. If G7 has an Euler cycle, then G has an Euler cycle. Important: if you answer “true,” then briefly explain why; if you answer “false,” then give a counterexample. Correct answers without an explanation  (or counterexample) will receive little partial credit.

QUEsTIoN 4 (12 points)

(a) Prove that the following graph does not contain a Hamilton circuit.

(b) Is the graph from part (a) planar or nonplanar? Why or why not? Correct answers without an explanation will receive little partial credit.

QUEsTIoN 5 (8 points)

(a) Kuratowski’s Theorem states that a graph G is planar if and only if

.

(b) State the definition of χ(G), the chromatic number of a graph G.

QUEsTIoN 6 (12 points) In class, I mentioned several times a corollary (and its contrapositive) to Euler’s Formula:

CoRoLLARy If G = (V, E) is a connected planar graph with e > 1, then e < 3v - 6, where e and v denote the number of edges and the number of vertices, respectively, in G.

(a) What is the contrapositive of this corollary?

(b) Suppose that a given graph G is connected.  How might you use the contrapositive in part (a) as a quick, easy check to determine if G fails to be planar?

(c) Assume that for a given connected graph G, it turns out that e 3v - 6.  Does this imply that G is planar? Briefly explain why or why not–you do not need to provide a counterexample or a proof. One sentence of justification will suffice.

QUEsTIoN 7 (10 points) Let G denote the following graph.  What is G’s chromatic number χ(G)? Justify your answer—show a coloring with χ(G) colors (label each vertex with a color) and argue (briefly) that fewer colors cannot suffice.

QUEsTIoN 8 (12 points) Model the following problem as a graph-coloring problem:  there are 59 computing jobs scheduled to be completed tomorrow on Wes’ supercomputer, SeaWulf.  The schedule, which states the start-time

and end-time during which job i is to be performed, i = 1, . . . , 59, is provided to us in advance.  Each job is to be assigned to one of 16 cores on Wes’ supercomputer, and at any time at most one job may be assigned to a core. (a) What do the vertices correspond to? What do the edges correspond to?

(b) What is being colored (vertices or edges)? What do different colors correspond to?

(c) Suppose I tell you that the graph is planar. Can all 59 jobs be completed tomorrow using 16 cores? Explain.

QUEsTIoN 9 (12 points) An icosahedron  is a Platonic solid which is intimately related to the dodecahedron we examined in class. From a graph-theoretic perspective, an icosahedron is a planar graph with 20 faces (i.e. regions), and each face is bounded by 3 edges. Show your work. Correct  answers  without  shown  work  will  receive  little partial credit.

(a) How many edges does an icosahedron have?

(b) How many vertices does an icosahedron have?