Math 301: Homework 9

Due: Friday, November 15, 2019

Reading: Read sections 8.1, 8.2, 8.3


  1. If a planar map has 46 vertices and 65 edges, how many faces must it have?

  2. Is it possible to find a set of 20 edges from \(K_{10}\), the complete graph on 10 vertices, such that if you remove those 20 edges then you obtain a planar graph? If so, draw such a graph as a planar map (with no edges crossing). If not, explain why not.

  3. Prove that the graph \(K_{3,3}\) is not planar without using Kuratowski’s theorem. Hint. Notice that there are no triangles (cycles of length 3) in the graph.

    K33 graph