Try It Now

Work these exercises to see how well you understand this material.

Solutions

  1. Answer: Theorem 9.6.12 can be applied to infer that if n ⩾ 5, then Kis nonplanar. A K4 is the largest complete planar graph.

  2. Answer:
    1. 4
    2. 3
    3. 3
    4. 3
    5. 2
    6. 4

  3. Answer: The chromatic number is n since every vertex is connected to every other vertex.

  4. Answer: Suppose that Gis not connected. Then Gis made up of 2 components that are planar graphs with less than k edges, G1 and G2. For i= 1,2 let vi, ri, and ebe the number of vertices, regions and edges in Gi. By the induction hypothesis, vi+ r− ei= 2 for i = 1,2.

    One of the regions, the infinite one, is common to both graphs. Therefore, when we add edge e back to the graph, we have r = r1 + r21, v = v1 + v2, and e = e1 + e2 + 1.

    \begin{align*} v+r-e &= (v_1 + v_2) + (r_1 + r_2 - 1) - (e_1 + e_2 + 1) \\ &= (v_1 + r_1 - e_1) + (v_2 + r_2 - e_2) - 2 \\ &= 2+2-2 \\ &= 2 \end{align*}

  5. Answer: Since |E| + E^c = \frac{n(n-1)}{2}, either E or Ehas at least \frac{n(n-1)}{4} elements. Assume that it is E that is larger. Since \frac{n(n-1)}{4} is greater than 3n − 6 for n ⩾ 11, G would be nonplanar. Of course, if Eis larger, then Gwould be nonplanar by the same reasoning. Can you find a graph with ten vertices such that it is planar and its complement is also planar?

  6. Answer: Suppose that ( V, E) is bipartite (with colors red and blue), |E|is odd, and (v1, v2, . . . , v2+ 1, v1) is a Hamiltonian circuit. If v1 is red, then v2+ 1 would also be red. But then {v2+ 1, v1} would not be in E, a contradiction.

  7. Answer: Draw a graph with one vertex for each edge, If two edges in the original graph meet at the same vertex, then draw an edge connecting the corresponding vertices in the new graph.