Why replace an edge by a path?
The edge bounds from Euler's formula give quick tests for nonplanarity, but they can miss a sparse graph. Imagine replacing each edge of by a two-edge path. The drawing still has the same essential connections, but nine new vertices make the usual numerical bounds much less restrictive. To turn this intuition into a proof, we must say exactly which paths replace the edges and why inserting or removing their internal vertices preserves planarity.
Throughout, graphs are finite, simple and undirected.
Definition 3.2.1
(Subdivisions and branch vertices)
A subdivision of a graph is obtained by replacing each edge by a – path of positive length, with the replacement paths internally vertex-disjoint and with no internal vertex among the original vertices of . A path of length one leaves its edge unchanged. The original vertices are called branch vertices. The internal vertices of each replacement path have degree two in the subdivision. These degree statements refer to the subdivision itself: a surrounding graph may have extra edges at those vertices.
Theorem 3.2.2
(Subdivision preserves planarity)
A finite simple graph is planar if and only if any subdivision of is planar.
Proof
(Marking points and concatenating arcs)
If has a plane embedding, mark the required number of distinct points in the interior of each edge arc and declare them vertices. The resulting arcs embed without introducing crossings.
Conversely, suppose has a plane embedding. For each replacement path, regard its consecutive edge arcs together as a single arc between its branch vertices, and cease treating the internal vertices as vertices. The path has no repeated vertex, so this concatenation is a simple arc. Different replacement paths meet only at common branch endpoints, since their internal vertices are disjoint and the embedding has no edge crossings. Thus the resulting drawing embeds exactly . Hence is planar. The argument also covers edges left unsubdivided and isolated vertices.
Proof X-ray
What makes the reverse direction work
The forward direction only marks points on arcs. The reverse direction is where the definition of a subdivision is used, and each clause has a job. That a replacement path has no repeated vertex makes the concatenated arcs a simple arc rather than a curve meeting itself. Internal disjointness, together with the absence of crossings in the embedding of , makes two concatenated arcs meet only at common branch vertices. That no internal vertex is an original vertex of prevents an arc from passing through a branch vertex. Drop internal disjointness and the argument fails at the second clause: in the star of the counterexample below, all nine paths pass through one vertex, and their concatenations would meet there.
Corollary 3.2.3
(Subdivision certificates of nonplanarity)
If a graph contains a subgraph that is a subdivision of a nonplanar graph , then is nonplanar.
Proof
(Restrict an embedding to the subgraph)
By the theorem the subdivision is nonplanar. If had a plane embedding, deleting all edges and vertices outside would leave a plane embedding of , a contradiction.
In practice a certificate is written in two parts. First specify the subgraph : give its branch vertices and one path for every edge of . Then check that distinct paths have no common internal vertex and contain no branch vertex internally. Extra edges in do not invalidate the certificate; simply omit them from the chosen subgraph.
The subgraph need not be induced. In particular, merely pointing to a set of vertices with many connections is not enough: the paths and their disjointness must be verifiable. Conversely, an extra edge between two chosen vertices is harmless when it is not used in the certificate.
What happens at a degree-two vertex?
The reverse direction does not ask us to move any curve. In the embedding of the subdivision, each edge is an arc; consecutive arcs of a replacement path meet at their common endpoint and nowhere else. Their union is therefore an arc, with the intermediate degree-two points now regarded as ordinary points of that arc. This operation is called suppressing those vertices. Since no other selected edge meets an internal vertex, no new intersection appears. If the vertex has more incident edges in the larger graph, first discard those extra edges: suppression is being applied to the selected subgraph, not necessarily to the whole graph.
It is equally useful to reverse the argument. Inserting a vertex on an edge increases both and by one. Consequently decreases by two, and decreases by one. Repeating the operation makes these necessary bounds easier to satisfy even though planarity has not changed. For the bipartite bound, check bipartiteness separately: subdividing only one edge can destroy it, as when a four-cycle becomes a five-cycle. Subdividing every edge once produces a bipartite graph, with old vertices in one part and new vertices in the other.
Subdivisions and minors
Definition 3.2.4
(Graph minors)
A minor is obtained by deleting vertices or edges and contracting edges, with loops deleted and parallel edges consolidated when returning to a simple graph.
Every subdivision of has as a minor: along each replacement path contract all but one edge, never identifying two branch vertices. Internal disjointness lets these contractions be performed independently. The reverse implication does not hold: take two adjacent degree-three vertices, each with two leaf neighbors. Contract their joining edge to obtain . The original tree has maximum degree three, however, so it cannot contain a subdivision of : the image of its center would need four distinct incident path edges. Thus a minor certificate and a subdivision certificate require different checks.
A sparse obstruction
Worked example 3.2.5
(Subdivide every edge of )
Let the two parts of be and . For each pair in the first part and in the second, introduce a distinct vertex and replace by . The resulting graph has vertices and edges. Its six branch vertices are ; its nine paths have distinct internal vertices. Thus is nonplanar because is nonplanar.
The ordinary planar bound would allow . Even the bipartite planar bound would allow . Indeed is bipartite: put all six original vertices on one side and all nine new vertices on the other. Neither inequality detects the obstruction. Now add a new leaf adjacent to and an extra edge . The larger graph remains nonplanar, because deleting the leaf and the extra edge leaves the same subdivision .
Counterexample mode
Paths that share an internal vertex do not suffice
Take six named vertices and a seventh vertex , with an edge from to each of the six. For every cross-pair such as there is a path , but all nine proposed paths use the same internal vertex . They do not form a subdivision of . In fact the graph is a star and is planar. Existence of a path for each pair, without the disjointness condition, cannot certify nonplanarity.
Two certificates written out
Worked example 3.2.6
(A subdivision hidden among extra edges)
Let the branch vertices be . Include the paths and , where are distinct new vertices. Include the other eight branch-to-branch edges directly. Also add the edge . There are ten required paths: two have internal vertex sets and , and the other eight have none. They therefore satisfy the subdivision conditions. Omit when selecting the certificate. The selected subgraph is a subdivision of , so the whole graph is nonplanar. The graph has eight vertices: five branch vertices and three internal vertices. The ten paths certify that every drawing must fail to be plane.
Worked example 3.2.7
(A certificate with unequal path lengths)
Take branch sets and . Use the nine paths
Assume are six distinct vertices outside the branch sets. Add an edge if desired. The nine paths cover exactly the nine cross-pairs, and their nonempty internal sets are , , , and , which are pairwise disjoint. The edge is omitted from the selected subgraph. Hence this is a subdivision certificate even though the larger graph contains an extra edge at two internal vertices. The selected subgraph has twelve vertices and fifteen edges; the ordinary planar bound allows , so that count alone proves nothing about its planarity.
A practical search starts by identifying possible branch vertices of sufficient degree, then tracing paths between them. Suppressing apparent degree-two chains in a drawing can reveal the candidate base graph, but the final proof should list the paths. In particular, degrees alone cannot certify a subdivision, and branch vertices may have additional neighbors in the surrounding graph.
Margin Note
Try the bipartite obstruction first in sparse graphs
A subdivision needs five branch vertices of degree at least four, while a subdivision needs only six of degree at least three. When few vertices have degree four, search for first.
What a certificate does and does not say
The two familiar base obstructions are and , whose nonplanarity follows from Euler's edge bounds. The preceding argument proves the useful one-way statement: a graph containing a subdivision of either is nonplanar. It does not, by itself, prove that every nonplanar graph contains such a subdivision. That converse is the deeper Kuratowski theorem and is not proved here. Failure to find a certificate is therefore not a plane embedding, and passing an edge-count test is not one either. To prove a graph planar, exhibit a crossing-free embedding or give another valid argument.
The same caution applies to contraction. Subdivision introduces degree-two vertices along edges; contracting an arbitrary edge of a larger graph is a different operation. A drawing may suggest a certificate, but the stated paths provide the checkable combinatorial evidence.
Common mistake
(Degrees alone do not certify a subdivision)
High degrees suggest candidate branch vertices but prove nothing. The octahedron graph, drawn as a triangle around a triangle with joined to , to and to , is planar by that drawing, yet each of its six vertices has degree four. Any five of them pass the degree test for branch vertices, but a planar graph contains no subdivision.
Common mistake
(Passing an edge-count test is not planarity)
The subdivided with vertices and edges satisfies both and , yet it is nonplanar. Edge bounds are necessary conditions only; to prove planarity, exhibit an embedding.
Exercises
Quick check
(Subdivide one edge of once. Find its numbers of vertices and edges, check the ordinary planar edge bound, and prove nonplanarity.)
Solution · Answer
There are six vertices and eleven edges: removing one edge and adding two raises the edge count from ten to eleven. The bound permits . Nevertheless, suppressing the new degree-two vertex recovers , so subdivision invariance proves nonplanarity.
Quick check
(Suppose a graph contains a subdivision of plus an extra edge between two internal vertices of distinct replacement paths. Explain why that extra edge does not spoil the certificate.)
Solution · Answer
Select the original subdivided paths and omit the extra edge from the subgraph. Their internal vertices remain pairwise disjoint within those paths. The selected subgraph is still a subdivision of , regardless of the degrees of those vertices in the larger graph.
Quick check
(Delete the edge from with parts and . Give a planar drawing description. Why does nonplanarity of not contradict your answer?)
Solution · Answer
Draw three internally disjoint paths , and as a planar theta-shaped graph. Place in a face between the first two paths and join it to and within that face without crossing. This is exactly . Deleting an edge can make a nonplanar graph planar; nonplanarity passes from a subgraph to a supergraph, not in the reverse direction.
Quick check
(A student claims that a planar graph can become nonplanar by subdividing one edge. Identify the failed step and justify the correct conclusion.)
Solution · Answer
Mark a new vertex in the interior of the edge arc of an existing planar embedding. The two resulting arcs introduce no crossing, so the subdivided graph remains planar. A different drawing with crossings would not disprove existence of this embedding.
Quick check
(Construct a graph that has as a minor but does not contain a subdivision of . Justify both claims.)
Solution · Answer
Join two degree-three vertices by an edge and attach two distinct leaves to each. Contracting the central edge produces a center adjacent to four leaves, giving . The original graph has maximum degree three, whereas the center of any subdivision must be incident with four distinct first path edges. Therefore no such subdivision is a subgraph.