Planar Graphs
Drawing a graph without crossing edges, Euler's formula relating vertices, edges and faces, and what that formula rules out.
5 exercises
Exercise 1
Is it possible for a planar graph to have 6 vertices, 10 edges and 5 faces? Explain.
Exercise 2
The graph has 6 vertices with degrees . How many edges does have? Could be planar? If so, how many faces would it have. If not, explain.
Exercise 6
I'm thinking of a polyhedron containing 12 faces. Seven are triangles and four are quadralaterals. The polyhedron has 11 vertices including those around the mystery face. How many sides does the last face have?
Exercise 8
Prove Euler's formula using induction on the number of edges in the graph.
Exercise 12
Prove that any planar graph with vertices and edges satisfies .
Adapted from Discrete Mathematics: An Open Introduction © 2013–2019 Oscar Levin. Licensed under CC BY-SA 4.0. Source: Discrete Mathematics: An Open Introduction. Imported at revision 1e2e26b.