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.
Prove that the graph below is not planar by finding a subdivision of \(K_5\) or \(K_{3,3}\) in it.
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?
For 266 students, based on the graduate reading: Show that the graph from question 2 is a string graph. (Hint: It is easier to do this using Theorem 16 of the reading and following the example of the Petersen graph in Figure 6 (left); if you do this, you do not need to find an explicit string representation.)