Math 301: Homework 9
Due: Friday, November 15, 2019
Reading: Read sections 8.1, 8.2, 8.3
Exercises:
-
If a planar map has 46 vertices and 65 edges, how many faces must it have?
-
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.
-
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.
