What a Subdivision Certificate Must Show
A Kuratowski subdivision can be easy to miss when some edges have been replaced by paths or when the graph has extra edges. The reliable check is to identify the branch vertices, then exhibit a path for each edge of \(K_5\) or \(K_{3,3}\). Those paths must not share internal vertices. The graph may contain other vertices and edges that are not used in the certificate.
All graphs in this tutorial are finite and simple. A path is a sequence of distinct vertices in which consecutive vertices are adjacent. The internal vertices of a path are its vertices other than its two endpoints. A family of paths is internally vertex-disjoint if no internal vertex of any path is an internal vertex of another path, and no internal vertex is an endpoint of another path.
For a subdivision of \(K_5\), there are five branch vertices and a path for each of the ten pairs of branch vertices. For a subdivision of \(K_{3,3}\), there are six branch vertices divided into two sets of three, and a path for each of the nine pairs with one endpoint in each set. There are no required paths between two branch vertices on the same side of \(K_{3,3}\).
Proof. Suppose first that a subgraph is a subdivision of \(K_5\) or \(K_{3,3}\). By the definition of subdivision, each edge of the original graph has been replaced by a path, and the replacement paths are internally vertex-disjoint. These paths and their endpoints give the stated subgraph. Conversely, suppose a subgraph has the stated branch vertices and paths. Keep just the edges and vertices on those paths, and omit any other edges of the subgraph. The paths give one replacement for each edge of \(K_5\) or \(K_{3,3}\); their internal disjointness ensures that the resulting graph is exactly a subdivision as defined. Thus the graph contains the required subdivision. \(\square\)
A useful necessary check follows from this description. In the subdivision subgraph itself, every branch vertex has degree \(4\) for a \(K_5\)-subdivision and degree \(3\) for a \(K_{3,3}\)-subdivision. Every non-branch vertex has degree \(2\). Degrees in the ambient graph can be larger, because unused edges may meet these vertices.
Proof. Each edge of \(H\) incident with a branch vertex \(v\) is replaced by one path beginning at \(v\), so it contributes exactly one incident edge at \(v\). No other replacement path has \(v\) as an internal vertex, by the definition of a subdivision. Therefore the degree of \(v\) in the subdivision is \(\deg_H(v)\). An inserted vertex is internal to one replacement path and belongs to no other path as an internal vertex or endpoint. It has exactly the two incident path edges, so its degree is \(2\). \(\square\)
Worked Certificates
Worked Example: A Subdivision of \(K_5\) with a Pendant Vertex
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,x,y,p\}\) and \(E=\{ac,ad,ae,bc,bd,be,ce,de,ax,xb,cy,yd,ap\}\). Find a \(K_5\)-subdivision.
Take \(a,b,c,d,e\) as branch vertices. The edge \(ab\) of \(K_5\) is represented by the path \(a,x,b\); the edge \(cd\) is represented by \(c,y,d\). The other eight pairs are represented by their direct edges:
| Branch pair | Representing path |
|---|---|
| \(ab\) | \(a,x,b\) |
| \(cd\) | \(c,y,d\) |
| \(ac,ad,ae,bc,bd,be,ce,de\) | The corresponding single-edge paths |
The internal vertices are \(x\) and \(y\), and they are distinct; neither is a branch vertex. Hence the ten paths are internally vertex-disjoint. The edge \(ap\) is not used, so \(p\) is not part of the certificate.
Check: the selected subgraph has \(5+2=7\) vertices. It has eight direct edges and two paths of length \(2\), so its edge count is \(8+2\cdot2=12\). A \(K_5\)-subdivision with two edges subdivided once has \(10+2=12\) edges. The selected degrees of \(a,b,c,d,e\) are each \(4\), and those of \(x,y\) are each \(2\), as required.
Worked Example: A Subdivision of \(K_{3,3}\) with an Extra Edge
Let \(G=(V,E)\), where \(V=\{u_1,u_2,u_3,v_1,v_2,v_3,x,y\}\), and \(E=\{u_1v_2,u_1v_3,u_2v_1,u_2v_2,u_2v_3,u_3v_1,u_3v_3,u_1x,xv_1,u_3y,yv_2,u_1u_2\}\). Find a \(K_{3,3}\)-subdivision.
Use \(U=\{u_1,u_2,u_3\}\) and \(W=\{v_1,v_2,v_3\}\) as the two branch sets. The required paths are all nine cross-pairs:
| Branch vertex in \(U\) | Paths to \(v_1,v_2,v_3\) |
|---|---|
| \(u_1\) | \(u_1,x,v_1\); \(u_1,v_2\); \(u_1,v_3\) |
| \(u_2\) | \(u_2,v_1\); \(u_2,v_2\); \(u_2,v_3\) |
| \(u_3\) | \(u_3,v_1\); \(u_3,y,v_2\); \(u_3,v_3\) |
The only internal vertices are \(x\) and \(y\), used on different paths. Neither is a branch vertex, so the paths satisfy the disjointness condition. The edge \(u_1u_2\) is an extra edge within \(U\), not one of the required \(K_{3,3}\) edges; omit it from the selected subgraph.
Check: the selected subdivision has \(6+2=8\) vertices. Seven required paths have length \(1\), and two have length \(2\), giving \(7+2\cdot2=11\) selected edges. This agrees with \(9+2=11\): \(K_{3,3}\) has nine edges, and the two length-\(2\) paths each add one edge and one vertex. Each branch vertex has selected degree \(3\), and \(x,y\) have selected degree \(2\).
Finding a Certificate When Degrees Mislead
Degree is a guide to candidate branch vertices, not a complete test. It is the degree in the selected subdivision that matters. Extra edges in the original graph can increase the ambient degree of a vertex that is an internal vertex of a subdivision path. In a search, first propose the branch vertices, then trace the required paths and check their interiors. Do not reject a candidate merely because the ambient graph has extra edges.
Worked Example: Extra Edges Between Internal Vertices
Let \(G=(V,E)\), where \(V=\{a,b,c,d,e,r,s,t\}\), and \(E=\{ac,ad,ae,bc,bd,be,ce,de,ar,rs,sb,ct,td,rt\}\). Show that \(G\) contains a \(K_5\)-subdivision even though two internal vertices have ambient degree \(3\).
Choose \(a,b,c,d,e\) as the branch vertices. Represent \(ab\) by \(a,r,s,b\), represent \(cd\) by \(c,t,d\), and represent the other eight pairs by direct edges \(ac,ad,ae,bc,bd,be,ce,de\). The internal vertices on the two longer paths are \(r,s\) and \(t\), respectively. These sets are disjoint, and none of these vertices is a branch vertex. Thus all ten replacement paths meet the proposition's conditions.
The extra edge \(rt\) is not part of the selected subgraph. In the ambient graph, \(r\) is incident with \(ar,rs,rt\), and \(t\) is incident with \(ct,td,rt\), so each has degree \(3\). In the selected subdivision, omit \(rt\); then \(r,s,t\) each have degree \(2\). The extra edge does not invalidate a subdivision, because the certificate is a subgraph and need not be induced.
Check: the selected subdivision has five branch vertices and three internal vertices, so it has \(5+3=8\) vertices. The path for \(ab\) has length \(3\), the path for \(cd\) has length \(2\), and the other eight paths have length \(1\). The selected edge count is \(3+2+8=13\). Starting from the ten edges of \(K_5\), the first path adds two edges and the second adds one, also giving \(10+2+1=13\).
Why the Verification Matters
Kuratowski's theorem, proved in the earlier material on Kuratowski's theorem, states that a finite graph is planar if and only if it contains no subdivision of \(K_5\) and no subdivision of \(K_{3,3}\). Consequently, a verified path system of either type is a nonplanarity certificate. To use this result, the certificate must actually meet the subdivision conditions; a suggestive drawing or a collection of paths that intersect internally is not enough.
For a proposed certificate, check the following in order:
- There are five distinct branch vertices for a proposed \(K_5\)-subdivision, or six distinct branch vertices with a specified split into two sets of three for a proposed \(K_{3,3}\)-subdivision.
- There is a path for every required pair: all ten pairs for \(K_5\), or all nine cross-pairs for \(K_{3,3}\).
- Every path uses edges of the given graph, and its endpoints are the intended branch vertices.
- No internal vertex is shared between paths or is itself a branch vertex.
- Any extra vertices or edges are left out of the selected subgraph. The certificate is not required to be induced.
A frequent mistake is to require the subdivision subgraph to contain every edge of the ambient graph between its chosen vertices. In the third example, that would force the extra edge \(rt\) into the candidate, although it is not a replacement for an edge of \(K_5\). The correction is to specify the selected subgraph explicitly and omit \(rt\). Another mistake is to count only the original edges after subdividing: replacing one edge by a path of length \(k\) adds \(k-1\) vertices and \(k-1\) edges, not zero edges. These counts are useful checks, but they do not replace checking the required paths and their disjointness.
Check Your Understanding
For each question, justify your answer by checking the branch vertices and representing paths, not just by counting degrees.
- In a subdivision of \(K_5\), one edge is replaced by a path of length \(4\), and every other edge remains a single edge. How many vertices and edges does the subdivision have?
- For a proposed \(K_{3,3}\)-subdivision, why are paths between branch vertices on the same side not required?
- Can an internal vertex of a selected subdivision have degree \(3\) in the ambient graph? Explain what happens to its degree in the selected subgraph.
- A graph has paths for all nine cross-pairs of six proposed \(K_{3,3}\) branch vertices, but two paths share an internal vertex. Does this verify a subdivision? Why or why not?
- Why does an extra edge between two vertices of a proposed subdivision not, by itself, invalidate the certificate?