# Why $K_5$ and $K_{3,3}$?

Most people will have already guessed that this is about Kuratowski's theorem.

The theorem states that every non-planar graph must contain a complete graph $$K_5$$ with five vertices or a complete bipartite graph $$K_{3,3}$$ with three vertices at each side - or subdivisions of these graphs.

I have seen a few proofs of this theorem (but not searched very much), but so far I have not found an explanation why exactly these two graphs occur in the theorem. What makes them so special?

Of course, $$K_5$$ is the smallest non-planar graph at all, but then, which role plays $$K_{3,3}$$ in the theorem?

Another approach, which I have tried a bit, was to search for properties that a minimal non-planar graph must have. In such a graph, no edge or vertex can be removed without making the graph non-planar, and no two edges which meet at a vertex of degree 2 can be unified. But this lead to no results, at least not for me.

So why do $$K_5$$ and $$K_{3,3}$$ occur in Kuratowski's theorem?

• They are minor-minimal non-planar graph (any proper minor of any of them is planar). Any other non-planar graph is not minor-minimal, since it contains $K_5$ or $K_{33}$ as a minor. Mar 4, 2021 at 20:28
• Once you recognize that the property of planarity is closed under graph minors, the Robertson-Seymour therorem guarantees you that there's some finite set of graphs such that any non-planar graph must contain (a subdivision of) one of them. Mar 4, 2021 at 20:58
• google.com/books/edition/Topological_Graph_Theory/… Mar 4, 2021 at 21:16
• $K_{3,3}$ is the smallest nonplanar graph if you're counting by the number of edges. Mar 5, 2021 at 14:28
• I think that rather than the number of edges, what's important about $K_{3,3}$ is that it is the smallest graph with all faces being of size at least 4. Mar 6, 2021 at 19:31