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?

  • 11
    $\begingroup$ 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. $\endgroup$ Mar 4, 2021 at 20:28
  • 4
    $\begingroup$ 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. $\endgroup$ Mar 4, 2021 at 20:58
  • $\begingroup$ google.com/books/edition/Topological_Graph_Theory/… $\endgroup$
    – Will Jagy
    Mar 4, 2021 at 21:16
  • 3
    $\begingroup$ $K_{3,3}$ is the smallest nonplanar graph if you're counting by the number of edges. $\endgroup$
    – lambda
    Mar 5, 2021 at 14:28
  • 1
    $\begingroup$ 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. $\endgroup$
    – domotorp
    Mar 6, 2021 at 19:31


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.