One of the properties of planar graphs from Monday's lecture is that every finite planar graph has degeneracy at most five, and in particular every finite planar graph has a vertex of degree at most five. This is also true, for instance, for the infinite planar graph formed by the vertices and edges of the familiar tiling of the plane by squares. Describe a different tiling of the plane whose vertices and edges form an infinite planar graph in which all vertices have degree greater than five.
The drawing below has one crossing. Prove that this crossing cannot be eliminated (the graph is not planar) by finding a subdivision of
A common way of drawing the complete graph on five vertices (with crossings) places its vertices at the five points of a regular pentagon, with ten edges: five edges on the sides of the regular pentagon, and five more edges on its diagonals.
The five edges on the sides of the pentagon form a cycle. Describe the flaps of this cycle, as defined in Wednesday's lecture (lecture 10b).
What is the compatibility graph of these flaps? Explain why this compatibility graph is not bipartite.
In any maximal planar graph, all faces are triangles. Is it also true that, in any maximal planar graph, all triangles are faces? Why or why not?