Part II · The Classic Theory

Planar Graphs

Created by Felipe Casadei

Some networks can be drawn flat with no wires crossing; most cannot. After this chapter you will be able to count the faces of any flat drawing with Euler's formula, name the only two graphs that ever stand between a network and a crossing-free drawing, and turn loops into cuts with plane duality.

Three houses, three utilities

Here is a puzzle that has circulated for over a century. Three houses each need a connection to three utility stations: water, gas, and electricity. Nine supply lines in total. Can you route all nine lines on flat ground so that no two lines cross?

Try it. Every attempt ends with eight lines placed and the ninth trapped: wherever it goes, it must cross something. The puzzle is not asking for cleverness; it is asking for something impossible, and by the middle of this chapter you will be able to prove that in four lines of arithmetic.

In graph language the puzzle is a specific graph: three vertices on one side, three on the other, and all nine possible edges between the sides. This is the complete bipartite graph \(K_{3,3}\) (read it as "K three three"): two groups of three, every cross-pair joined, no edges inside a group. The puzzle asks whether \(K_{3,3}\) can be drawn in the plane so that edges meet only at their shared endpoints. Graphs that can be drawn that way are called planar, and this whole chapter, following Chapter 4 of Diestel's book^[2], is about them.

The chapter builds up four very different answers to the question "which graphs are planar?": a counting law (Euler's formula), a pair of forbidden patterns (Kuratowski's theorem), a statement in linear algebra (MacLane's theorem), and even a statement about orderings (Schnyder's theorem). The same class of graphs, described in the languages of geometry, combinatorics, algebra, and order theory. Along the way we will meet plane duality, the swap of vertices and faces that Chapter 5 will use for map colouring and Chapter 6 for flows.

Plane or planar? A picture versus a possibility

The first distinction of the chapter is small but load-bearing, and mixing it up is the single most common beginner error. A plane graph is an actual picture: specific points in the plane serving as vertices, specific curves serving as edges, no two curves crossing. A planar graph is an abstract graph, a bare list of vertices and edges, which could be drawn as a plane graph. Plane is a property of a drawing; planar is a property of a graph.

Why does the difference matter? Because one abstract graph has many drawings, and a bad drawing proves nothing. Take \(K^4\), the complete graph on four vertices: four dots, all six pairs joined. (Diestel writes complete graphs as \(K^n\); many other books write \(K_n\). Same object.) Drawn as a square with both diagonals, \(K^4\) shows a crossing. Drawn as a triangle with the fourth vertex inside, it shows none. The first picture is not a plane graph; the second is; the abstract graph \(K^4\) is planar either way.

This raises a subtler question that Section 4.3 of the book takes seriously: if one graph has many drawings, when should two drawings count as "the same drawing"? Hold that thought; we first need faces and Euler's formula.

New notation in this chapter

Rows marked "reminder" were introduced in Chapter 1 and return here in a load-bearing role.

A small toolkit from the geometry of the plane

Before graphs can live in the plane, we need a few honest facts about the plane itself. Diestel collects them in Section 4.1^[1], states them precisely, and does not prove them, because the proofs are topology, not graph theory. We follow suit.

Why only piecewise-straight curves? Because any crossing-free drawing can be straightened into one, and restricting to them keeps every topological statement elementary. Nothing is lost and much wildness is avoided.

Two more notions. For an open set \(O\) of the plane, a region of \(O\) is a maximal connected chunk: a set of points of \(O\) any two of which can be linked by an arc staying inside \(O\). The frontier of a set \(X\) is its boundary line: all points \(y\) such that every small disc around \(y\) meets both \(X\) and the rest of the plane. The frontier of an open disc, for example, is its bounding circle. One notational care: Diestel keeps \(\setminus\) for differences of point sets in the plane (so \(\mathbb{R}^2 \setminus G\) is "the plane minus the drawing") and the minus sign for graph deletion (so \(G - e\) is "the graph with edge \(e\) removed").

The engine behind everything else is a statement so obvious-sounding that its actual content is easy to miss.

In words: a closed non-self-crossing loop cuts the plane into exactly an inside and an outside, and the loop is the complete border of both. Nearly every proof in this chapter reduces at some point to "this point is inside, that point is outside, so any arc between them must cross the loop." Two companion facts get used just as often. First, three arcs sharing both endpoints but otherwise disjoint carve the plane into exactly three regions, and any arc through the middle region between points of the two outer arcs must cross the middle arc (Lemma 4.1.2). Second, an arc drawn across a region does not split that region if it merely hangs there connecting two blobs of the frontier (Lemma 4.1.3): arcs, unlike polygons, do not separate. Cycles enclose; paths do not.

Plane graphs and their faces

Now the main object, with all its fine print.

A plane graph is simultaneously a picture and a graph: the same letter \(G\) names the abstract graph and the set of points of the plane covered by the drawing. That double life is deliberate, and the point-set reading is what makes the next definition work.

That the boundary of a face really is a subgraph, never half an edge, is a theorem, not part of the definition. The key local fact (Diestel's Lemma 4.2.2^[2]) says three things. If the frontier of a face contains any interior point of an edge \(e\), it contains all of \(e\). If \(e\) lies on a cycle, then \(e\) borders exactly two faces. And if \(e\) lies on no cycle, it borders exactly one. The proof idea is pleasantly local: around any interior point of \(e\), take a disc so small it meets the drawing only in \(e\); the disc is cut into two half-discs, each sitting inside some face, so at most two faces touch \(e\) there. If \(e\) lies on a cycle, the Jordan curve theorem puts the two half-discs on opposite sides of that cycle, in different faces: a cycle edge is a wall between two rooms. If \(e\) is a bridge, the arc-does-not-separate lemma says both half-discs belong to one face: a bridge is a wall jutting into the middle of a single room.

Several structural facts now fall out, each one a small step toward Euler's formula and Whitney's theorem.

Forests enclose nothing. A plane forest (a drawing of a cycle-free graph) has exactly one face (Proposition 4.2.4): with no cycles there are no walls that close, so no territory ever gets enclosed. This will be the base case of Euler's formula.

Only a cycle has two rooms with the same wall. If two distinct faces have exactly the same boundary, the whole graph is just a cycle (Lemma 4.2.5). In every richer graph, a face is pinned down by its boundary; this uniqueness matters when we later match up faces of different drawings.

In 2-connected graphs, faces are bounded by cycles. Recall from Chapter 3 that a graph is 2-connected when it is connected, has at least three vertices, and stays connected after deleting any one vertex; such graphs are built by starting from a cycle and repeatedly gluing on paths. Each glued path lands inside some face and splits it into two, and both new faces inherit cycle boundaries. Hence every face of a 2-connected plane graph is bounded by a cycle (Proposition 4.2.6).

In 3-connected graphs, you can spot the face boundaries without looking at the picture. This is the quiet star of the chapter (Proposition 4.2.7): in a 3-connected plane graph (deleting any two vertices leaves it connected), the face boundaries are precisely the non-separating induced cycles, that is, the cycles with no chord whose deletion leaves the rest of the graph connected. Both properties are purely combinatorial: they mention no drawing. One direction: a chordless cycle that separates nothing can have graph-stuff on only one of its two sides, by the Jordan curve theorem, so its other side is a bare face. The other direction: a face boundary cannot have a chord (the chord and a connecting path would be forced to cross) and cannot separate the graph (Menger's theorem from Chapter 3 supplies three independent paths, one of which dodges the face entirely). Keep this in your pocket: it is the whole proof of Whitney's uniqueness theorem below.

For at least three vertices, these two conditions coincide (Proposition 4.2.8): a picture is full exactly when every room, the infinite one included, is triangular. One direction is immediate: in a triangular room, all three boundary vertices are already pairwise adjacent, so no new edge fits. The converse takes the Jordan machinery: a bigger room always leaves space for a chord.

Euler's formula: one law that rules every drawing

Now a theorem of 1752, and still the only purely quantitative law of planarity.

Pause on what is being claimed. The number of faces is a property of a particular picture, yet the formula says the picture does not matter: \(\ell = 2 - n + m\) is decided by the abstract graph alone. Every drawing of a given connected planar graph has the same number of faces.

The proof idea is an induction on the number of edges, with \(n\) fixed. If the connected graph has no cycle, it is a tree: \(m = n - 1\) edges (from Chapter 1) and, since forests enclose nothing, one face; the sum is \(n - (n-1) + 1 = 2\). Otherwise pick an edge lying on a cycle and delete it. That edge was a wall between two distinct rooms; deleting it merges them into one. So \(m\) drops by one, \(\ell\) drops by one, and the alternating sum \(n - m + \ell\) does not move. Walk the induction down to a tree and you are done. The careful bookkeeping ("exactly two faces merge into exactly one") is precisely the wall-between-two-rooms fact from the previous section.

From one line of arithmetic, an avalanche of consequences.

Proof idea: count edge-face incidences twice. Every face is bounded by at least 3 edges; every edge borders at most 2 faces; therefore \(3\ell \le 2m\), in words: three times the faces is at most twice the edges. Substitute \(\ell \le \tfrac{2}{3}m\) into Euler's formula and solve: \(m \le 3n - 6\). The striking consequence: planar graphs are sparse. However enormous, a planar graph averages fewer than six edge-ends per vertex, so it always has a vertex of degree at most 5, a fact Chapter 5 will lean on for colouring.

And the bound draws blood immediately. Consider \(K^5\), the complete graph on five vertices: \(n = 5\) allows at most \(3 \cdot 5 - 6 = 9\) edges, but \(K^5\) has \(\binom{5}{2} = 10\). One edge over budget. No drawing exists.

What about the utilities graph? \(K_{3,3}\) has \(n = 6\) and \(m = 9\), comfortably under \(3 \cdot 6 - 6 = 12\), so the plain bound says nothing. But \(K_{3,3}\) is bipartite, so it contains no triangle: its shortest cycles have length 4. Rerun the double count with rooms of at least 4 walls: \(4\ell \le 2m\), which with Euler gives \(m \le 2n - 4\) for triangle-free planar graphs. For \(K_{3,3}\) that allows at most \(2 \cdot 6 - 4 = 8\) edges. It has 9. The houses cannot be wired, and that is the whole proof.

One step further, at no extra cost. Subdividing an edge (replacing it by a path through new vertices) clearly cannot rescue planarity: a drawing of the subdivided graph would yield a drawing of the original by ignoring the new dots along the way. So no plane graph contains a subdivision \(TK^5\) or \(TK_{3,3}\), a stretched copy of either culprit, as a subgraph (Corollary 4.2.11). This is the easy half of Kuratowski's theorem. The astonishing half, that these two are the only obstacles, comes two sections from now.

When are two drawings the same drawing?

Back to the question we parked earlier. An abstract planar graph can be drawn in many ways. When should two drawings count as genuinely different, and when are they merely the same picture wiggled about? Diestel's Section 4.3^[3] offers three answers of decreasing strictness, then shows they mostly collapse into one. (The book marks this section as skippable on a first pass; read it as the chapter's philosophical hinge, where topology hands over to combinatorics.)

First, the strictest: two plane graphs are topologically isomorphic if a continuous deformation of the whole sphere carries one drawing onto the other. (The sphere, not the plane, so that an inner face of one drawing is allowed to correspond to the outer face of the other; on the sphere the outer face is not special.) Second: they are combinatorially isomorphic if some isomorphism between the underlying graphs extends to their faces, matching face to face so that a vertex or edge lies on the boundary of a face exactly when its image lies on the boundary of the matching face. Third, and weakest: they are graph-theoretically isomorphic if an isomorphism maps the collection of face-bounding subgraphs of one drawing onto that of the other, without even tracking which subgraph bounds which face.

Theorem 4.3.1 collapses the ladder: the weakest notion already implies the middle one (the face matching reappears for free, uniquely unless the graph is a cycle, because faces are pinned down by their boundaries), and for 2-connected graphs the middle notion implies the strongest. The proof of that last step builds a sphere deformation piece by piece: match the vertices, then bend each edge onto its partner edge, then fill in each face using the Jordan–Schoenflies theorem, which extends a correspondence between two circles to the discs they bound. This is where 2-connectedness earns its keep: face boundaries are then genuine cycles, i.e. circles, exactly what the filling theorem needs.

So for 2-connected graphs, "same face structure" and "deformable into each other" are one notion, and we simply call two embeddings of the same graph equivalent when the canonical correspondence between the two drawings is such an isomorphism. Can inequivalent drawings actually happen? Yes, easily, once the graph has weak points:

The appendages in Figure 4.6 can be flipped into different faces because a single vertex, \(x\), is the only anchor holding them. 3-connectedness removes exactly this freedom, and then something remarkable happens:

The proof is three lines, because all the work is already done. By Theorem 4.3.1 it suffices to check the weakest condition: that face-bounding cycles map to face-bounding cycles. But in a 3-connected plane graph, "bounds a face" means "is a non-separating induced cycle", and that is an abstract property of the graph, preserved by every isomorphism. Done. The drawing was never a free choice; it was encoded in the abstract graph all along.

Kuratowski's theorem: exactly two obstacles

We know two culprits: no planar graph contains a stretched \(K^5\) or a stretched \(K_{3,3}\). Kuratowski's theorem is the converse, and it deserves a moment of awe before the details: among all the infinitely many graphs, exactly two are responsible for every failure of planarity, ever. Any non-planar graph, however enormous, contains a stretched copy of one of them.

Two containment notions from Chapter 1 need re-glossing, because the theorem uses both. \(G\) contains \(X\) as a topological minor if \(G\) has a subgraph that is a subdivision \(TX\): a copy of \(X\) whose edges have been stretched into paths through new in-between vertices. \(G\) contains \(X\) as a minor if \(X\) can be obtained from a subgraph of \(G\) by contracting connected chunks of vertices into single points. Minor containment is the more generous notion: every topological minor is a minor, but not conversely. For our two culprits, however, the notions coincide (Lemma 4.4.2): a graph has a \(K^5\) or \(K_{3,3}\) minor if and only if it has one of them as a topological minor. The reason, in brief: \(K_{3,3}\) has maximum degree 3, and minors of maximum degree at most 3 are automatically topological (a Chapter 1 fact); and a smallest possible \(K^5\) minor either has star-shaped branch chunks, making it a genuine \(TK^5\), or hides a \(K_{3,3}\) minor inside instead.

The proof runs through 3-connectedness, and its heart is a drawing argument worth seeing (Lemma 4.4.3): every 3-connected graph without a \(K^5\) or \(K_{3,3}\) minor is planar. Induct on the number of vertices. Chapter 3 supplies the crucial tool: every 3-connected graph on more than four vertices has an edge \(xy\) whose contraction (merging \(x\) and \(y\) into one vertex) leaves it 3-connected. Contract it; the smaller graph has no forbidden minor either, so by induction it has a drawing. Now delete the merged vertex from that drawing. It sat inside some face of the rest, and since the rest is 2-connected, that face is bounded by a cycle \(C\), with all the former neighbours of \(x\) and of \(y\) sitting on \(C\). Re-read the drawing as a drawing of \(G - y\) with \(x\) at the merged position. It remains to place \(y\). The neighbours of \(x\) chop \(C\) into arcs. If all of \(y\)'s neighbours happen to lie on a single one of those arcs, there is a free pocket beside that arc, and \(y\) drops in with room to spare (Figure 4.8). If not, a short case analysis shows the graph was guilty all along: two of \(y\)'s neighbours interleaved around \(C\) with two of \(x\)'s produce a \(TK_{3,3}\), and \(x\), \(y\) sharing three neighbours on \(C\) produces a \(TK^5\). Contradiction, so the good case is the only case.

The general case then reduces to the 3-connected one by a purely combinatorial argument (Lemmas 4.4.4 and 4.4.5): take a graph with as many edges as possible subject to containing no \(TK^5\) or \(TK_{3,3}\); such an edge-maximal graph, it turns out, is automatically 3-connected once it has at least four vertices. Pumping a Kuratowski-free graph full of edges welds it together. So the 3-connected case was the general case in disguise, and the theorem follows. (Diestel states Lemma 4.4.4 in more generality than needed here, on purpose: Chapter 7 reuses it for extremal problems.)

Three tidy consequences round off the section. First (Proposition 4.4.1): a maximal plane graph, one whose particular drawing is full, is always maximally planar, meaning no edge can be added in any drawing. You can never get stuck by drawing badly. Second, also 4.4.1: a planar graph with \(n \ge 3\) vertices is maximally planar exactly when it has exactly \(3n - 6\) edges; the extremal count is drawing-independent. Third (Corollary 4.4.7): every maximal planar graph with at least four vertices is 3-connected, so by Whitney it has essentially one drawing. Triangulations are the rigid skeletons of the planar world.

Planarity without pictures: algebra and order

Everything so far has been geometric. Diestel's Section 4.5^[5] presents two characterizations of planarity in which no drawing appears at all, and they are among the strangest facts in the book.

Recall the cycle space from Chapter 1: \(\mathcal{C}(G)\), the vector space over the two-element field whose vectors are edge sets, spanned by the edge sets of cycles, where adding two edge sets means taking their symmetric difference (keep the edges in exactly one of the two sets). Its dimension is \(m - n + 1\) for a connected graph: edges, minus vertices, plus one.

Where would such a basis come from? From the faces, of course. In a 2-connected plane graph, the boundaries of the inner faces are cycles, they generate the whole cycle space (the inner face boundaries lying inside any cycle sum to that cycle, because shared interior edges cancel in pairs), and each edge borders at most two faces, so no edge lies in more than two of them. Drawing a graph hands you a sparse basis for free. Figure 4.9 shows the smallest interesting case.

The converse direction is where it gets clever. Sparse bases survive edge deletion (delete an edge and drop, or merge, the one or two basis cycles that used it), so it is enough to show that the two Kuratowski graphs have no sparse basis; then any graph with a sparse basis avoids them as topological minors, and Kuratowski's theorem finishes the job. And the culprits fail by bare counting. For \(K^5\): the cycle space has dimension \(10 - 5 + 1 = 6\); take a supposed sparse basis of 6 cycles, add to the list the sum of all 6; now 7 nonempty edge sets, each a cycle-like set of at least 3 edges, need at least 21 edge-slots, but sparseness plus the extra set caps the total at twice the number of edges, \(2 \cdot 10 = 20\). For \(K_{3,3}\): dimension \(9 - 6 + 1 = 4\); shortest cycles have length 4 (its girth); five sets of size at least 4 need 20 slots, but only \(2 \cdot 9 = 18\) exist. Planarity, decided by linear algebra.

A cousin of MacLane's criterion, for 3-connected graphs, is Kelmans' theorem (1978, often called Tutte's planarity criterion; Diestel 4.5.2): a 3-connected graph is planar if and only if every edge lies on at most (equivalently, exactly) two non-separating induced cycles.^[5] The forward direction you already believe: those cycles are exactly the face boundaries, and every edge is a wall between exactly two rooms. The backward direction is two big theorems shaking hands: Tutte's theorem from Chapter 3 says the non-separating induced cycles generate the whole cycle space of a 3-connected graph, and if each edge lies on at most two of them, that generating family contains a sparse basis, so MacLane applies. Count chordless cycles, conclude drawability.

The last characterization is the strangest, and Diestel states it without proof.

Sit with that. Form the humblest possible order, "this vertex is an endpoint of this edge", and ask how many total orderings are needed to pin it down. Three or fewer: planar. Four or more: not planar. No topology, no algebra, no drawing; pure order theory detects exactly the graphs that can be drawn flat. Beyond the book, the technique behind Schnyder's proof also yields straight-line drawings of planar graphs on small grids, which is why it shows up inside practical graph-layout software.

Plane duality: swapping vertices and faces

The chapter closes with its most elegant construction. Look at any map: countries, borders, and corner points where borders meet. Now put a capital city inside each country and join capitals of neighbouring countries by a road crossing their shared border. The map of capitals and roads is a new graph, born from the faces of the old one. That is plane duality.

One technicality first. The dual construction produces loops (an edge from a vertex back to itself) and parallel edges (several edges with the same two endpoints), which our definition of plane graphs banned. So Diestel widens the frame^[6]: a plane multigraph is like a plane graph except that an edge may also be a closed loop (a polygon touching exactly one vertex), and distinct edges may share both endpoints. Loops and parallel pairs count as cycles. Without this generality the theory collapses; you will see why in Figure 4.10.

Vertex counts and face counts swap while the edge count stays put. The drawn cube (Figure 4.3) has 8 vertices, 12 edges, 6 faces; its dual, one vertex per face, is the octahedron: 6 vertices, 12 edges, 8 faces. Euler's formula is symmetric under the swap, as it must be.

Now the punchline the picture is hinting at. Recall from Chapter 1 that a cut is the set of edges running between the two sides of a vertex partition, and a bond is a minimal nonempty cut: a cut no proper nonempty part of which is itself a cut.

The proof idea is the Jordan curve theorem doing what it does best. A cycle in \(G\) splits the plane into inside and outside. Every face of \(G\) lies wholly in one or the other, so the dual vertices split into two camps, and the dual edges crossing the cycle are precisely the edges between the camps: a cut, and a minimal one, since walking between faces on the same side never crosses the cycle. Conversely, a dual bond traps a set of faces, and the frontier of the trapped territory is a cycle. Loops and bridges echo the correspondence at its degenerate end: a bridge lies on no cycle, and its dual, a loop, lies in no bond.

The cycle–bond exchange suggests a purely combinatorial definition, with no drawing mentioned at all: call a multigraph \(G^*\) an abstract dual of \(G\) if it has the same edge set as \(G\) and its bonds are precisely the edge sets of cycles of \(G\). If an abstract dual exists, then the cut space of \(G^*\) (spanned by its bonds) coincides, as a set of edge sets, with the cycle space of \(G\) (Proposition 4.6.2); the relationship is symmetric, and one can pass back and forth. And then, the closing theorem:

Forward: draw the graph, take the plane dual of each component, done, by the cycle–bond correspondence. Backward, a two-step gem: if an abstract dual exists, the cycle space of \(G\) equals the cut space of \(G^*\); the cut space always has a sparse generating family, namely the stars \(E(v)\) of edges around single vertices, because every edge has exactly two ends and so lies in at most two stars; a sparse generating family contains a sparse basis; and a sparse basis means planar, by MacLane. The circle closes: drawings, forbidden minors, sparse bases, poset dimension, and now duality, five languages all naming the same class of graphs.

Where planarity goes from here

Kuratowski's theorem is the prototype of a grand theme. It says the planar graphs, a class closed under taking minors, are characterized by a finite list of forbidden minors: \(\{K^5, K_{3,3}\}\). The Robertson–Seymour graph minor theorem, the summit of Chapter 12, generalizes this beyond recognition: every minor-closed class of graphs has such a finite forbidden list. Graphs drawable on a torus, on a pretzel surface, on anything: finite list, always. Euler's formula generalizes to those surfaces too, with the constant 2 replaced by a number measuring the surface's complexity. What this chapter did for the plane by hand, Chapter 12 does for all surfaces by structure theory, and planarity is where that story learned to walk.

More immediately: Chapter 5 needs the degree-at-most-5 vertex that the edge bound guarantees, and the triangulation structure, to prove the five colour theorem. Everything you just built gets used on the very next page of the course.