What a Kuratowski Subdivision Certifies
A graph can be nonplanar even when it does not contain all the edges of \(K_5\) or \(K_{3,3}\) directly. Some of those edges may instead be represented by longer paths. The important requirement is that the paths fit together like the edges of one of these two graphs: their endpoints are the correct branch vertices, and their internal vertices do not overlap. Such a structure is a certificate of nonplanarity.
All graphs in this tutorial are finite and simple. A graph is planar if it can be drawn in the plane with vertices represented by distinct points and edges by arcs whose interiors do not intersect other edges or vertices. A particular crossing-free drawing is a plane embedding. The drawing is not part of the abstract graph; planarity means that at least one such drawing exists.
The internal vertices of these paths may be extra vertices of \(G\); they do not represent vertices of \(H\). The certificate does not require the subdivision to be an induced subgraph: \(G\) may have additional edges between vertices in the certificate, or edges leading to vertices outside it. Only the listed paths and their edges are used.
For \(K_5\), a certificate has five distinct branch vertices and ten paths, one for each pair of branch vertices. For \(K_{3,3}\), it has two groups of three branch vertices and nine paths, one for each pair with one endpoint in each group. In either case, checking the path lists verifies a concrete subgraph rather than relying on a drawing.
Why the Certificate Forces Nonplanarity
The supporting obstruction facts are that \(K_5\) and \(K_{3,3}\) are nonplanar. They follow from the planar edge bounds established using Euler’s formula. A simple planar graph with \(n\geq 3\) vertices has at most \(3n-6\) edges, so a planar \(K_5\) would have at most \(3(5)-6=9\) edges, whereas it has \(10\). A simple bipartite planar graph with \(n\geq 3\) vertices has at most \(2n-4\) edges, so a planar \(K_{3,3}\) would have at most \(2(6)-4=8\) edges, whereas it has \(3\cdot3=9\). These bounds rule out plane embeddings of the two base graphs.
Proof. Suppose \(G\) has a plane embedding. Restrict that embedding to the subgraph consisting of the branch vertices and the paths of the claimed subdivision; deleting other vertices and edges cannot create crossings. At each internal vertex of a listed path, exactly two edges of this subgraph meet. In the restricted embedding, replace the two consecutive edge-arcs through that vertex by their concatenation. Repeating this for all internal vertices leaves one arc for each edge of the base graph. The path interiors were disjoint from one another and from all branch vertices, so the resulting arcs intersect only at the common endpoints prescribed by the base graph. They therefore give a plane embedding of \(K_5\) or \(K_{3,3}\). This contradicts the nonplanarity of that base graph. Thus \(G\) is nonplanar. \(\square\)
The argument works because planarity would survive the two operations being used: first restrict to the certificate subgraph, then suppress the internal degree-two vertices on its paths. It does not say that every graph with many edges is nonplanar, or that finding the certificate is the only way to prove nonplanarity.
A Practical Certificate Check
For an explicit list, check the same conditions in a fixed order. First identify the proposed branch vertices and, for \(K_{3,3}\), the two parts. Next check that each required pair has exactly one listed path. Then verify each consecutive pair of vertices on every path is an edge of \(G\). Finally check that paths have no repeated vertices and that different paths have no shared internal vertices. A missing base edge or a shared internal vertex invalidates the proposed subdivision, even if the list looks suggestive.
For a \(K_5\) certificate, account for all ten unordered pairs among five branch vertices. For a \(K_{3,3}\) certificate, account for all nine cross-part pairs.
For a path \(v_0,\ldots,v_k\), confirm \(v_{i-1}v_i\in E(G)\) for each \(i=1,\ldots,k\).
Each path must be simple, and no internal vertex may be used by another path or be a branch vertex.
Once the required paths are verified, the theorem proves \(G\) nonplanar; no planar drawing test is needed.
Worked Certificates
Worked Example: A Subdivided \(K_5\)
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,x\}\) and \(E=\{ax,xb,ac,ad,ae,bc,bd,be,cd,ce,de\}\). Verify a \(K_5\) subdivision.
Take \(a,b,c,d,e\) as the branch vertices. The ten required paths, indexed by their endpoint pairs, are \(ab:a-x-b\), \(ac:a-c\), \(ad:a-d\), \(ae:a-e\), \(bc:b-c\), \(bd:b-d\), \(be:b-e\), \(cd:c-d\), \(ce:c-e\), and \(de:d-e\).
The path \(a-x-b\) uses edges \(ax\) and \(xb\), both in \(E\). Each of the other nine paths uses its single listed edge, and those edges are \(ac,ad,ae,bc,bd,be,cd,ce,de\), all in \(E\). The only internal vertex of any path is \(x\), on the \(ab\) path alone. Thus all ten paths meet the subdivision conditions, and the five branch vertices are distinct.
Check: \(K_5\) has \(\binom{5}{2}=5\cdot4/2=10\) edges, and the list contains ten endpoint pairs. The subdivision uses eleven edges: the nine direct paths contribute \(9\), and \(a-x-b\) contributes \(2\), giving \(9+2=11\). The theorem therefore certifies that \(G\) is nonplanar. The extra vertex \(x\) does not change which graph the paths represent; it subdivides the edge \(ab\).
Worked Example: A Subdivided \(K_{3,3}\)
Let \(G=(V,E)\), where \(V=\{a_1,a_2,a_3,b_1,b_2,b_3,x,y\}\) and \(E=\{a_1x,xb_1,a_1b_2,a_1b_3,a_2b_1,a_2b_2,a_2b_3,a_3b_1,a_3y,yb_2,a_3b_3\}\). Use parts \(A=\{a_1,a_2,a_3\}\) and \(B=\{b_1,b_2,b_3\}\).
For the cross-part pairs, list the paths \(a_1b_1:a_1-x-b_1\), \(a_1b_2:a_1-b_2\), \(a_1b_3:a_1-b_3\); \(a_2b_1:a_2-b_1\), \(a_2b_2:a_2-b_2\), \(a_2b_3:a_2-b_3\); and \(a_3b_1:a_3-b_1\), \(a_3b_2:a_3-y-b_2\), \(a_3b_3:a_3-b_3\).
The two longer paths use \(a_1x,xb_1\) and \(a_3y,yb_2\), respectively. The other seven paths use the seven remaining listed direct cross-part edges. The internal vertices \(x\) and \(y\) are distinct and occur on only one path each; no path has a repeated vertex. This verifies all \(3\cdot3=9\) required pairs.
Check: the seven direct paths contribute \(7\) edges and the two longer paths contribute \(2+2=4\), for \(7+4=11\) edges in the certificate. Starting with \(K_{3,3}\)’s \(9\) edges and replacing two edges by paths with one extra edge each also gives \(9+1+1=11\). The verified subdivision makes \(G\) nonplanar.
Worked Example: Extra Edges Do Not Invalidate a Certificate
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,x,z\}\) and \(E=\{ax,xb,ac,ad,ae,bc,bd,be,cd,ce,de,xc,az\}\). A proposed certificate lists \(a-x-b\) for the pair \(ab\), and direct one-edge paths for \(ac,ad,ae,bc,bd,be,cd,ce,de\), using \(a,b,c,d,e\) as branch vertices.
For the \(ab\) path, both \(ax\) and \(xb\) are in \(E\). The nine direct paths use \(ac,ad,ae,bc,bd,be,cd,ce,de\), also all in \(E\). The only internal vertex is \(x\), and it is used only on the \(ab\) path. Thus the list is a valid \(K_5\) subdivision. The other two edges, \(xc\) and \(az\), need not be included in the certificate subgraph.
Check: there are \(11\) edges in the subdivided \(K_5\) certificate and \(2\) additional edges, so \(|E|=11+2=13\). The branch-pair count remains \(9+1=10\) paths: nine direct paths and one path of length two. Extra edges do not change those path checks, so \(G\) is nonplanar.
Common Pitfalls and Why Certificates Matter
Passing an edge bound does not prove planarity. In the first example, \(n=6\) and \(m=11\), while the simple planar bound gives \(3n-6=3(6)-6=12\). The inequality \(11\leq12\) holds. The incorrect conclusion would be “therefore \(G\) is planar.” The bound is only a necessary condition: a planar graph must satisfy it, but a nonplanar graph can satisfy it too. The explicit \(K_5\) subdivision is a valid obstruction even though this particular edge count does not rule out planarity.
Do not list an edge that is absent. In the first example, writing \(a-b\) as the path for the pair \(ab\) would fail because \(ab\notin E\). The correction is the path \(a-x-b\), whose two consecutive edges are both present. Checking paths edge by edge catches this error.
Do not require the certificate to be induced. The extra edges in the third example are irrelevant to the listed paths. The certificate is a subgraph, so its edges need not be every edge of \(G\) between its vertices. What matters is that the selected paths form the required subdivision and obey the disjointness conditions.
These checks make a certificate independently auditable: its vertices, paths, and edge membership can all be confirmed from the lists. Once verified, the theorem converts that finite check into a proof of nonplanarity. This direction is one part of Kuratowski’s theorem; the converse, that every nonplanar graph contains such a subdivision, requires a separate argument.
Check Your Understanding
For each question, justify your answer using the definitions and certificate conditions above.
- What must be checked to verify that ten listed paths form a subdivision of \(K_5\)?
- Suppose two paths representing different edges of a proposed subdivision share an internal vertex. Which certificate condition fails?
- A graph contains a verified subdivision of \(K_{3,3}\) and also has additional edges between vertices of the certificate. Does the subdivision still certify nonplanarity? Explain.
- Why does satisfying \(m\leq 3n-6\) not establish that a simple graph is planar?
- In the second worked example, which two \(K_{3,3}\) edges are represented by paths of length two, and how many edges does the certificate use altogether?