display | more...

In the mathematical field of graph theory, Kuratowski's theorem gives a characterization of planar graphs in terms of forbidden subgraphs.

First, some notation. Recall that a graph G is a pair (V, E) consisting of a finite set V of "vertices" and a collection E of 2-element subsets of V, called "edges". Here's a graph: ({1,2,3,4,5}, {{1,2}, {2,3}, {3,5}, {2,5}}). We might pictorially represent this graph as follows:

(1)    (5)      
 |    .'|       
 |  .'  |    (4)
 |.'    |       

Two vertices are said to be adjacent if they are the endpoints of an edge. The degree of a vertex vV is the number of vertices adjacent to v. A cycle is a connected subgraph which is 2-regular, that is, every vertex in the cycle has degree 2. A path is a connected subgraph of a cycle which is not the entire cycle.

A subdivision (sometimes called a homeomorph) of a graph G is any graph obtained from G by adding in any number of vertices of degree two along each edge. Equivalently, it is the graph G but with the edges replaced by paths of arbitrary length. As an example, the following is a subdivision of the graph example above:

(1)        (5)      
 |        .'|       
 |      .' (*)      
(*)   .'    |    (4)
 |  .'     (*)      
 |.'        |       

A graph is planar if it can be drawn in the plane without crossing edges. This can and usually is made more precise*, but this is really all just in an attempt to codify the intuitive meaning.

Kuratowski's theorem states that a graph G is planar iff it contains no subgraph isomorphic to a subdivision of the complete graph K5 or of the complete bipartite graph K3,3.

The complete graph K5 is a graph on five vertices where every vertex is connected to every other. The complete bipartite graph K3,3 has the vertex set {a1, a2, a3, b1, b2, b3}, and the edges are exactly those 2-element subsets of vertices containing an ai and a bj. See below for an attempt at an ASCII art rendering:

      _.-' / \ '-._                        (a_1)_       (a_2)       _(a_3)
  _.-'    /   \    '-._                      | '.'-._  .' | '.  _.-'.' |  
(2)______/_____\______(5)                    |   '.  :'._ | _.':  .'   |  
 \'-._  /       \  _.-'/                     |     ::   _:+:_   ::     |  
  \   'X._     _.X'   /                      |   .' _:.'  |  '.:_ '.   |  
   \  /   '-.-'   \  /                       | .'.-'   '. | .'   '-.'. |  
    \/ _.-'   '-._ \/                      (b_1)        (b_2)        (b_3)
           K5                                           K3,3             

It's fairly easy to see that neither of the above graphs are planar—I invite the reader to play around with them. The nonplanarity of K3,3 in particular is the core of a famous puzzle, called the 'Sewer, Water, and Electricity' or the 'Three Utilities' puzzle, which challenges you to find a planar embedding of K3,3 (the punchline being that it's impossible). Likewise, any graph containing a subdivision of either of these graphs cannot be planar either, as such a planar embedding could be used to embed K5 or K3,3 themselves in the plane.

The challenge of proving Kuratowski's Theorem is showing the other direction, that each nonplanar graph has a subdivision of either K5 or K3,3 as a subgraph. One common approach begins by investigating the cycles in a graph, and what subgraphs the cycle separates the graph into: the structures left behind by splitting up a planar graph on any of its cycles need to be compatible with each other in a specific way, since the embedding of that cycle must be a closed loop in the plane, and by the Jordan curve theorem this loop has an inside and an outside. After playing with the concept enough, one finds a way to say that graphs which aren't planar have a cycle where the compatibility just mentioned fails to hold, and then either the structure there has enough bits to look like K5, or else has to contain a subdivision of K3,3.

Occasionally misattributed to Kuratowski is the related result called Wagner's theorem, which states that every nonplanar graph has at least one of K5 or K3,3 as a minor.

If e = {u,v} ∈ E is an edge of some graph G = (V, E), then G delete e is the graph G\e = (V, E - {e}) obtained by simply removing e, and G contract e is the graph G/e with vertex set (V - {u,v}) ∪ {•} and where every edge that was adjacent to u or v in G is now adjacent to the new vertex •. Any graph that can be obtained from G by a sequence of edge deletions, edge contractions, and thrown-away neighbourless vertices is called a minor of G.

Any graph that has a subgraph isomorphic to a subdivision of G has G as a minor, obtained by deleting everything that isn't the subdivision subgraph, and then contracting all the subdivided edges down to single edges. Hence, by Kuratowski's theorem, nonplanar graphs must have at least one of K5 or K3,3 as a minor. It is also not too hard to show that, if a graph has K3,3 as a minor, then it has a subdivision of K3,3 as a subgraph. Also, if a graph has K5 as a minor but no subdivision of K5 as a subgraph, then it must contain a subdivision of K3,3.

This shows Wagner's Theorem is equivalent to Kuratowski's Theorem. Many graph theorists prefer Wagner's version, because taking minors is a very versatile operation, and due to a huge and powerful result of Robertson and Seymour called the graph minors theorem, it is known that "is a minor of" is a well-quasi-ordering, that is, a particularly nice kind of ordering operation with deep implications for graphs as objects.

* A planar embedding of G = (V, E) is an injective function φ : VR2 together with, for every edge e = {u,v} ∈ E, a plane curve with endpoints φ(u) and φ(v), such that no two such plane curves intersect except possibly at their endpoints.

Log in or register to write something here or to contact authors.