Kuratowski's Theorem: Characterizing Planar Graphs

This article explores Kuratowski's theorem, a fundamental result in graph theory that determines whether a mathematical graph can be drawn on a flat plane without any intersecting edges. It covers the basic definition of planar graphs, introduces the two specific "forbidden" graphs known as \(K_5\) and \(K_{3,3}\), explains the concept of graph subdivisions, and demonstrates how Kuratowski's theorem combines these elements to provide a definitive, structural test for graph planarity.

What is a Planar Graph?

In mathematics, a graph is a collection of points, called vertices, connected by lines, called edges. A graph is defined as planar if it can be drawn on a flat, two-dimensional surface in such a way that no two edges cross each other, except at the vertices where they connect.

Simply looking at a drawing of a graph with crossing edges does not mean the graph is non-planar; it might just be drawn poorly. Moving the vertices around and rerouting the edges might eliminate the crossings. Planarity is a property of the graph's underlying structure, not a specific drawing of it.

The Two Forbidden Graphs: \(K_5\) and \(K_{3,3}\)

To understand why some graphs can never be untangled on a flat plane, you only need to look at two specific non-planar graphs. These are the smallest and most basic non-planar graphs in mathematics:

  1. The Complete Graph of Five Vertices (\(K_5\)): This graph consists of 5 vertices where every single vertex is directly connected to every other vertex, resulting in a total of 10 edges. If you try to draw this on a piece of paper, you can easily connect four vertices without crossing lines, but connecting the fifth vertex to all four others will inevitably force at least one edge to cross another.
  2. The Complete Bipartite Graph (\(K_{3,3}\)): Often called the "Utility Graph," this consists of 6 vertices divided into two groups of three (commonly imagined as three houses and three utilities: water, gas, and electricity). Every vertex in the first group must connect to every vertex in the second group, totaling 9 edges. No matter how you route the lines on a flat plane, the ninth connection will always have to cross an existing line.

Understanding Graph Subdivisions

Before stating the theorem, it is necessary to understand a graph operation called subdivision.

Subdividing a graph means taking an existing edge and inserting one or more new vertices along that line. For example, if vertex A connects to vertex B, placing a new vertex C in the middle of that line turns the single edge (A-B) into a path of two edges (A-C-B).

Adding vertices along an edge does not change the fundamental shape or untangle a graph. Therefore, if a graph cannot be drawn without crossings, subdividing its edges will not help; the resulting graph will still be non-planar.

How Kuratowski's Theorem Works

Published by Polish mathematician Kazimierz Kuratowski in 1930, Kuratowski's theorem completely characterizes planar graphs by linking them to \(K_5\), \(K_{3,3}\), and subdivisions.

The Theorem States: A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of \(K_5\) or \(K_{3,3}\).

A subgraph is simply a smaller graph formed from a subset of the vertices and edges of a larger graph. Kuratowski's theorem translates a geometric drawing problem into a purely structural one. Instead of endlessly trying to redraw a complex graph to see if the edges can be uncrossed, you only need to search the graph's structure:

  • When a graph is non-planar: Somewhere inside the graph, hiding among its vertices and edges, there is an exact copy of \(K_5\) or \(K_{3,3}\) (or a version of them that has been stretched out by adding extra vertices along their edges). Because that hidden piece cannot be drawn flat, the entire graph cannot be drawn flat.
  • When a graph is planar: If you search the entire graph and find that it does not contain a subdivided \(K_5\) or \(K_{3,3}\) within it, the theorem guarantees that the graph can be drawn on a flat plane without any edges intersecting.