DA4 - Proving non-planarity

Subdivisions of K5 and K3,3

Replace one edge of $K_{3,3}$ by two edges meeting at a new vertex. Can this extra vertex make the graph planar? The edge count has changed, so the earlier numerical test may no longer settle the question, but the underlying obstruction survives.

Recall the two non-planar graphs proved using Euler's bounds: $K_5$ joins all pairs of five vertices, while $K_{3,3}$ joins every pair across two sets of three. A subdivision replaces edges of one of these graphs by paths, inserting new degree-2 vertices. The original vertices are called branch vertices. Different replacement paths may meet at their shared branch endpoints, but must not share an internal vertex; their internal vertices are new and are not branch vertices.

An edge may remain unsubdivided, so the original graph itself counts as a subdivision with no inserted vertices. Inserting $s$ vertices in total increases both V and E by $s$, because each insertion replaces one edge by two. It preserves $V-E$, but can disguise degrees and cycle lengths.

[DIAGRAM: asset_name: Forbidden graph subdivisions; asset_slug: aqa7367-kuratowski-subdivisions; caption: A new degree-2 vertex changes an edge into a path without removing the forbidden pattern; description: Left is K3,3 on branch groups A B C and X Y Z except AX is replaced by AP PX. Right is K5 on A B C D E except AB is replaced by AP PB. The new vertex P is shaded clay in each separate graph. Crossings without labelled dots are not vertices.]

Use the identical insertion operation on the other forbidden graph. Its branch degrees differ, but the new vertex still has degree 2.

A subdivision of a bipartite graph need not itself be bipartite. In Worked example 1, A–P–X–B–Y–A is a 5-cycle. The inserted vertex lengthens a former even cycle by one. Therefore you cannot apply the bipartite edge bound merely because the graph arose from $K_{3,3}$. The subdivision structure, rather than the inherited name, is what matters.

Count a longer fresh replacement path.

Internally disjoint replacement paths

A convincing subdivision certificate names the branch vertices and gives a separate route for every required edge of the smaller forbidden graph.

For $K_{3,3}$, choose groups $\{A,B,C\}$ and $\{X,Y,Z\}$, then supply nine paths: one for each cross-group pair. For $K_5$, choose five branch vertices and supply ten paths: one for each unordered pair. The interior of each path must contain no branch vertex, and no vertex may lie inside two of the selected paths. “Internally disjoint” allows paths to share a branch endpoint when the original edges did so.

The larger graph may contain extra edges or vertices. Delete them when choosing the subgraph that forms the subdivision. A vertex of degree 3 in the original graph can become a degree-2 internal vertex after an unwanted edge is deleted. Degrees relevant to the subdivision are degrees within the selected subgraph.

Now subdivide a second edge and introduce a distracting edge between the two internal vertices. Deleting that distraction is part of the proof.

[DIAGRAM: asset_name: Finding an obstruction inside a larger graph; asset_slug: aqa7367-kuratowski-paths; caption: Delete PQ before reading P and Q as internal vertices of the selected subdivision; description: Left has all K3,3 cross-pairs on groups A B C and X Y Z except AX and CZ, replaced respectively by AP PX and CQ QZ, with an extra edge PQ. Right removes PQ. The nine selected paths are APX AY AZ BX BY BZ CX CY CQZ; their only internal vertices P and Q are distinct.]

A list such as A–P–X and B–P–Y would fail this certificate if P were internal to both paths. The paths would merge at a vertex that should not be shared. Similarly, a proposed path through a third branch vertex is invalid for a single replaced edge: it combines two intended connections. A path certificate avoids these errors more reliably than saying a drawing “looks like” a familiar graph.

Supply a fresh certificate from a complete edge list.

Kuratowski’s theorem

Kuratowski's theorem turns a verified subdivision into a conclusive obstruction to every possible plane embedding.