7
$\begingroup$

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?

$\endgroup$
11
  • 14
    $\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
  • 5
    $\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
  • 8
    $\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
  • 2
    $\begingroup$ @domotorp: in what sense does $K_{3,3}$ have faces? It is non-planar... $\endgroup$ Mar 8, 2021 at 2:25

1 Answer 1

8
$\begingroup$

I have now found a paper by A. Skopenkov where he proves the theorem from the fact that $K_5$ and $K_{3,3}$ are the only graphs $G$ with the property

For each edge $x y$, the Graph $G - x - y$ does not contain a $\theta$-graph and has no vertex of degree 1.

where $G - x - y$ is the graph $G$ with the vertices $x$ and $y$ removed. This is at least a starting point for finding what makes $K_5$ and $K_{3,3}$ so special.

Edit: Corrected the statement of the characterisation $K_5$ and $K_{3,3}$.

$\endgroup$
4
  • 1
    $\begingroup$ It seems to me that the cube graph has this property as well. $\endgroup$
    – M. Winter
    Nov 27, 2023 at 19:04
  • 1
    $\begingroup$ No. Remove an edge and you get two squares that overlap at one edge — which is a graph that is a subdivision of $K_{2,3}$. $\endgroup$
    – rimu
    Nov 27, 2023 at 19:09
  • 2
    $\begingroup$ Correct me, but two overlapping squares are outerplanar, and outerplanar graphs do not contain $K_{2,3}$ as a minor. $\endgroup$
    – M. Winter
    Nov 27, 2023 at 21:33
  • $\begingroup$ You are right, I'll correct the statement of the theorem. (The original statement in the text does not have this problem. $\endgroup$
    – rimu
    Nov 28, 2023 at 19:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.