Why Maximal Planar Subgraphs Help
A nonplanar graph can contain a large planar subgraph, and the edges left out of that subgraph record where planarity fails. The useful choice is an edge-maximal planar spanning subgraph: it includes every vertex, is planar, and cannot have another edge of the original graph added while remaining planar. The spanning requirement matters. In particular, it prevents an argument from mistaking a nonplanar graph with an extra isolated vertex for a graph that is minimal among all its nonplanar subgraphs.
All graphs in this tutorial are finite and simple. A plane graph is a planar graph together with a fixed embedding in the plane. A face is a connected region of the complement of that embedding. Vertices incident with a face are vertices appearing on its boundary; a boundary walk may repeat vertices. An H-bridge of a subgraph \(H\) is either an edge of \(G\) not in \(H\), with both endpoints in \(H\), or a component of \(G-V(H)\) together with all its edges to \(H\). Its vertices in \(H\) are its attachments. For a spanning subgraph, all bridges are single omitted edges.
Such an \(H\) always exists: start with the spanning graph on \(V(G)\) having no edges, which is planar, and add edges of \(G\) whenever planarity is preserved. Since \(G\) has finitely many edges, the process stops. The result is edge-maximal by its stopping rule.
What Maximality Says About Attachments
Proof. Suppose an omitted edge \(uv\) has both endpoints incident with a face \(F\). Inside \(F\), draw an arc from \(u\) to \(v\) whose interior lies entirely in \(F\). If a vertex occurs more than once on the boundary walk, choose the boundary occurrences corresponding to the incidences of \(F\). The new arc has no intersection with the embedded graph except at \(u\) and \(v\), so it gives a plane embedding of \(H+uv\). This contradicts edge-maximality. Therefore no omitted edge has both endpoints incident with one face. \(\square\)
This conclusion concerns the chosen embedding: it rules out adding an omitted edge inside one of its faces. It is not a claim that every pair of vertices not cofacial in this embedding is nonadjacent in \(G\). Nor does it say that each bridge, considered separately, is nonplanar. It says that an omitted edge cannot be drawn in that particular face without changing the embedding.
Worked Example: A Maximal Spanning Subgraph of K5
Let \(G\) have \(V(G)=\{1,2,3,4,5\}\) and \(E(G)=\{12,13,14,15,23,24,25,34,35,45\}\), so \(G=K_5\). Let \(H\) have the same vertices and all these edges except \(45\).
To verify that \(H\) is planar, draw the triangle \(123\), put vertex \(4\) inside it and join \(4\) to \(1,2,3\), then put vertex \(5\) outside the triangle and join \(5\) to \(1,2,3\) in the exterior region. These edges give \(12,13,23,14,24,34,15,25,35\), exactly \(E(H)\), with no crossings. Thus \(H\) is planar.
The only edge of \(G\) missing from \(H\) is \(45\). If \(45\) could be added while keeping the graph planar, the resulting graph would be \(K_5\), which is nonplanar. Hence \(H\) is edge-maximal planar in \(G\). In any fixed plane embedding of \(H\), vertices \(4\) and \(5\) cannot be incident with a common face: if they were, the proposition would allow \(45\) to be drawn in that face.
Check: \(H\) has \(10-1=9\) edges, and \(G\) has \(10\) edges, one for each unordered pair of its five vertices. The sole omitted edge is therefore \(45\), as claimed. The argument uses the established nonplanarity of \(K_5\), not a face-count calculation for a particular drawing.
The Reduction Statement and Its Scope
The proposition above is a constraint on individual omitted edges. It is not, on its own, a proof of the reduction lemma. The global step must analyze how bridges and their attachments interact with paths in the planar subgraph. In particular, choosing several paths that meet and then splitting them at a meeting point does not automatically preserve the required connections between attachment vertices. A valid reduction must establish the actual internally disjoint paths that realize the subdivision.
The standard reduction result is useful here as a named theorem whose proof is supplied in the subsequent treatment of Kuratowski’s theorem. This tutorial uses it only in that explicit form: it does not infer a K5 or K3,3 subdivision from an unverified attachment sketch. The examples below illustrate two concrete, directly checkable subdivision certificates and the sort of attachment data that a reduction must ultimately justify.
Reading Explicit Attachment Patterns
Worked Example: Three Omitted Edges Complete a K3,3
Let \(H\) have vertices \(\{a_1,a_2,a_3,b_1,b_2,b_3\}\) and edges \(\{a_1b_1,a_1b_3,a_2b_1,a_2b_2,a_3b_2,a_3b_3\}\). These edges form the 6-cycle \(a_1,b_1,a_2,b_2,a_3,b_3,a_1\), so \(H\) is planar. Let \(G\) have the same vertices and also the edges \(a_1b_2,a_2b_3,a_3b_1\).
In \(G\), every \(a_i\) is adjacent to every \(b_j\). For \(a_1\), the neighbors are \(b_1,b_2,b_3\); for \(a_2\), they are \(b_1,b_2,b_3\); and for \(a_3\), they are \(b_1,b_2,b_3\). There are no edges within either triple. Thus \(G=K_{3,3}\), and the three added edges are three single-edge bridges of \(H\), each attached at its two endpoints.
The identity map on the six vertices and nine edges exhibits \(G\) itself as a subdivision of \(K_{3,3}\): every corresponding path has length \(1\), so there are no internal vertices to check. Hence \(G\) is nonplanar by the established nonplanarity of \(K_{3,3}\). This explicit verification establishes a subdivision in this example; it does not assert that every three omitted edges in every plane graph produce one.
Check: \(H\) has \(6\) edges, namely the six listed cycle edges. The added set has \(3\) edges, and none is in \(E(H)\): \(a_1b_2\), \(a_2b_3\), and \(a_3b_1\) are precisely the three missing pairs across the two vertex classes. Therefore \(|E(G)|=6+3=9\), the number of pairs in \(K_{3,3}\), since \(3\cdot3=9\).
Worked Example: A K5 Subdivision Inside a Graph with an Isolated Vertex
Let \(G\) have \(V(G)=\{1,2,3,4,5,6\}\) and \(E(G)=\{12,13,14,15,23,24,25,34,35,45\}\). Vertex \(6\) is isolated. The subgraph induced by \(\{1,2,3,4,5\}\) is \(K_5\), because its edge set contains all ten pairs among those five vertices.
The identity map on vertices \(1,2,3,4,5\) and their ten edges is a subdivision of \(K_5\), with every replacement path of length \(1\). Thus \(G\) contains a K5 subdivision and is nonplanar. Adding an isolated vertex does not remove that obstruction: any plane embedding of \(G\) would restrict to a plane embedding of its subgraph \(K_5\).
This example explains why one must be careful with minimality. Deleting any edge from \(K_5\) gives a planar graph, so \(G\) is edge-minimal nonplanar in the sense that deleting any one of its edges makes the graph planar; the isolated vertex remains. Nevertheless, \(G\) has the proper nonplanar subgraph \(K_5\), obtained by omitting vertex \(6\). Edge-minimality alone therefore does not imply that every proper nonplanar subgraph is impossible.
Check: There are \(\binom{5}{2}=5\cdot4/2=10\) possible edges among vertices \(1,\ldots,5\), and all ten appear in the stated list. No listed edge uses vertex \(6\), so it is isolated.
Minimality Without the Isolated-Vertex Error
When a proof needs a minimal counterexample, it must specify the order being minimized and verify that the chosen notion of minimality has the required consequences. A safe option for a fixed graph \(G\) is to minimize over its spanning subgraphs: every candidate has vertex set \(V(G)\), and only edges are removed. If a spanning nonplanar subgraph is minimal under edge deletion, then deleting any one of its edges makes it planar. This conclusion does not rule out a nonplanar subgraph formed by omitting an isolated vertex; that possibility is irrelevant to minimality among spanning subgraphs.
Alternatively, if minimality is taken among all nonplanar subgraphs by inclusion, a proper nonplanar subgraph might omit a vertex without omitting an edge. The K5-plus-isolated-vertex example shows exactly why that argument cannot be replaced by the phrase “edge-minimal, hence no proper nonplanar subgraph.” The missing vertex must be dealt with, or the chosen minimality must be changed.
Why the Reduction Matters
The bridge viewpoint organizes the proof problem. The planar subgraph supplies a fixed embedding and its faces; bridges supply the missing connections and their attachment vertices. Edge-maximality immediately rules out the simplest obstruction to maximality—an omitted edge drawable inside one face. The reduction lemma addresses the harder question: when the attachments cannot be accommodated consistently, what explicit nonplanar subgraph is forced?
Once a subdivision is actually exhibited, it is a certificate of nonplanarity. Subdividing edges preserves the obstruction: if a subdivision of \(K_5\) or \(K_{3,3}\) had a plane embedding, suppressing the internal degree-two vertices on its replacement paths would give a plane embedding of \(K_5\) or \(K_{3,3}\), respectively. This uses the standard suppression operation on paths whose internal vertices have degree two and lie on no other selected path. Since both base graphs are nonplanar, neither subdivision is planar.
Common pitfall. A cyclic ordering of attachments can suggest that two added routes “cross” in one chosen drawing. That observation alone does not prove the resulting abstract graph is nonplanar: the graph may have a different embedding. To certify nonplanarity, identify branch vertices and list the internally disjoint paths for a K5 or K3,3 subdivision, or apply a stated theorem whose hypotheses have been checked. Likewise, a purported list of missing edges must be compared against the actual edge set before it is used.
Check Your Understanding
For each question, distinguish the direct face argument from the global bridge-reduction step.
- Why does an omitted edge whose endpoints are incident with a common face contradict edge-maximality in the fixed embedding?
- What is the difference between an edge-maximal planar spanning subgraph and a planar subgraph with the largest possible number of edges?
- In the K3,3 example, list the three omitted edges and verify that each joins one \(a_i\) to one \(b_j\).
- Why does K5 together with an isolated vertex show that edge-minimal nonplanarity does not exclude proper nonplanar subgraphs?
- Why is it not enough to say that several paths can be split at an intersection to obtain the paths of a subdivision?