Why K5 and K3,3 Minors Obstruct Planarity

Why These Two Minors Matter

A minor is obtained from a graph by deleting vertices, deleting edges and contracting edges. These operations can make a graph smaller while preserving a crucial feature: if the original graph is planar, every graph obtained this way is planar too. This gives a useful obstruction. If a graph can be reduced to a known nonplanar graph by minor operations, then the original graph could not have been planar.

We will establish the obstruction for \(K_5\) and \(K_{3,3}\). The key ingredients are the preservation of planarity under each operation and two edge-count bounds obtained from Euler’s formula. All graphs in this tutorial are finite and simple unless an operation temporarily creates loops or multiple edges.

Deletion and contraction are distinct operations. Deleting an edge removes it but keeps its endpoints; deleting a vertex removes that vertex and every incident edge. Contracting an edge merges its endpoints, so edges previously incident with either endpoint become incident with the merged vertex. A graph is a minor of itself, using a sequence of zero operations.

Planarity Survives Minor Operations

Proof. Start with a plane drawing of a planar graph \(G\). Deleting an edge means erasing its drawing, so creates no crossings. Deleting a vertex means erasing that vertex and all its incident edges, again creating no crossings. For an edge contraction, take a sufficiently small neighborhood of the drawn edge and its endpoints that contains no other vertices and meets other edges only in short initial segments at those endpoints. Shrink the drawn edge to a point inside this neighborhood and attach the incident segments to that point in their existing order. This gives a drawing of the contracted graph without crossings. If contraction creates a loop or multiple edges, removing those edges preserves planarity. Each operation therefore preserves planarity, and applying the argument successively proves the claim for any finite sequence of operations. \(\square\)

This proposition gives a contrapositive test: if a minor of \(G\) is nonplanar, then \(G\) is nonplanar. To use that test, we first verify the nonplanarity of the two particular graphs.

Euler’s Formula Gives Edge Bounds

We use Euler’s formula for a connected plane graph: if it has \(n\) vertices, \(m\) edges and \(f\) faces, then \(n-m+f=2\). This is the standard Euler formula for plane graphs. In any plane drawing, the sum of the lengths of the facial boundary walks is \(2m\), since each edge has two sides and each side is counted along a face boundary.

Proof. First suppose the graph is connected and take a plane drawing. Since it is simple, no facial boundary walk has length \(1\). A facial boundary walk of length \(2\) would traverse one edge in both directions; for the walk to return immediately along that edge at both endpoints, each endpoint must have degree \(1\). In a connected graph this would make the whole graph a single edge, contradicting \(n\ge3\). Thus every face boundary walk has length at least \(3\). Consequently \(3f\le2m\). Euler’s formula gives \(f=2-n+m\), so \(3(2-n+m)\le2m\), which rearranges to \(m\le3n-6\).

If the graph is disconnected, connect its components by adding edges drawn through the unbounded face, one edge at a time, without crossings, until the graph is connected. This can be done by placing the component drawings in disjoint regions and joining them outside the drawings. The resulting simple planar graph has the same \(n\) and at least as many edges as the original. The connected case bounds its edge count by \(3n-6\), so the original graph also has at most \(3n-6\) edges. \(\square\)

A stronger bound applies to bipartite planar graphs. A graph is bipartite if its vertices can be partitioned into two sets so that every edge joins different sets. Every closed walk in a bipartite graph has even length, because its vertices alternate between the two sets.

Proof. First suppose the graph is connected. If it is a tree, it has \(m=n-1\) edges, and \(n-1\le2n-4\) because \(n\ge3\). Otherwise use a plane drawing. Every facial boundary walk has even length, since the graph is bipartite. No such walk has length \(2\): as in the preceding proof, a length-\(2\) facial walk forces a connected graph to consist of a single edge, whereas here \(n\ge3\). Thus every face boundary walk has length at least \(4\), giving \(4f\le2m\). Euler’s formula yields \(4(2-n+m)\le2m\), and therefore \(m\le2n-4\).

For a disconnected graph, join its components by edges drawn without crossings until it is connected. The added edges can be chosen to join opposite parts of the bipartition: when joining two components, interchange the names of the two parts in one component if necessary. The resulting graph is still simple, bipartite and planar, with the same \(n\) and at least the original number of edges. The connected bound proves the stated bound for the original graph. \(\square\)

The Two Obstructions

Proof. The complete graph \(K_5\) has \(n=5\) vertices and \(m=5\cdot4/2=10\) edges, since each of its five vertices is adjacent to the other four and each edge is counted at both endpoints. If \(K_5\) were planar, the first edge bound would give \(m\le3(5)-6=9\), contradicting \(m=10\).

The graph \(K_{3,3}\) has two parts of size \(3\), with every vertex in one part adjacent to all three vertices in the other and no edges within either part. Thus it is bipartite, has \(n=3+3=6\) vertices and \(m=3\cdot3=9\) edges. If it were planar, the bipartite edge bound would give \(m\le2(6)-4=8\), contradicting \(m=9\). Hence both graphs are nonplanar. \(\square\)

Using the Obstruction Correctly

The reasoning has a fixed direction: a planar graph has only planar minors. Therefore finding a \(K_5\) or \(K_{3,3}\) minor proves nonplanarity. The result is an obstruction test, not by itself a test that certifies planarity: failing to find either minor in a particular search does not establish that the graph is planar.

A minor can be present without appearing as an unchanged subgraph. Contraction may combine several vertices into one, as in the split-vertex example. Conversely, an edge subdivision can conceal a familiar graph until a path is contracted. When checking a proposed certificate, specify the actual deletions and contractions, and verify that the resulting vertices and edges are exactly those of the claimed minor.

Common mistake: the bound \(m\le3n-6\) alone does not rule out \(K_{3,3}\). Substituting its values gives \(9\le3(6)-6=12\), which is true and yields no contradiction. The correction is to use the bipartite bound: \(m\le2n-4=2(6)-4=8\), whereas \(K_{3,3}\) has \(9\) edges. The sharper bound depends on bipartiteness; it cannot be applied to an arbitrary planar graph.