Lesson 1

Below we give without proof two criteria for graph planarity. Both say that in a certain sense, the minimal non-planar graphs \(K_{5}\) and \(K_{3,3}\) are the only obstructions to planarity.

A subdivision of a graph \(G\) is a graph obtained from \(G\) by repeatedly replacing an edge \(\{u,v\}\) with a pair of edges \(\{u,w\}\) and \(\{w,v\}\), where \(w\) is a new vertex. For example, the graph shown below is a subdivision of \(K_{3,3}\).