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?

Improve this question
$\endgroup$
11
  • 15
    $\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$
    – Fedor Petrov
    Commented 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$
    – Steven Stadnicki
    Commented 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
    Commented 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
    Commented Mar 6, 2021 at 19:31
  • 2
    $\begingroup$ @domotorp: in what sense does $K_{3,3}$ have faces? It is non-planar... $\endgroup$
    – Sam Hopkins
    Commented Mar 8, 2021 at 2:25

1 Answer 1

Reset to default
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}$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ It seems to me that the cube graph has this property as well. $\endgroup$
    – M. Winter
    Commented 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
    Commented 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
    Commented 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
    Commented Nov 28, 2023 at 19:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .