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?

somefinite set of graphs such that any non-planar graph must contain (a subdivision of) one of them. $\endgroup$edges. $\endgroup$smallestgraph with all faces being of size at least 4. $\endgroup$6more comments