Planar graphs and Euler’s formula

A graph is planar if it can be drawn in the plane with no two edges crossing. Circuit boards, road maps and the layout of chips on a wafer all raise the question of whether a network can be drawn without crossings, and if not, how few crossings are possible. Planar graphs have remarkably rigid structure. A single equation, Euler's formula, forces them to be sparse, rules out the graphs \(K_5\) and \(K_{3,3}\), and leads to the classification of the regular polyhedra known to the ancient Greeks. It is also the starting point for the coloring results of lesson 9.

Plane drawings and faces

A plane drawing, or embedding, of a graph places the vertices at distinct points and the edges as curves that meet only at shared endpoints. A planar graph may have many different embeddings. Removing the drawing from the plane leaves a number of connected regions called faces, exactly one of which is unbounded, the outer face. The boundary of each face is a closed walk in the graph, and its length, counting an edge twice if the face lies on both of its sides, is the degree of the face.

Every edge contributes 2 to the total of the face degrees, once for each side. This is the face version of the handshake lemma: \[\sum_{f}\deg f = 2E.\] A tree has a single face, whose boundary walk traverses each edge twice.

Euler's formula

Theorem (Euler). If a connected planar graph has a plane drawing with \(V\) vertices, \(E\) edges and \(F\) faces, then \[V - E + F = 2.\]

Proof. Induct on the number of edges for a fixed \(V\). A connected graph has at least \(V - 1\) edges. If \(E = V - 1\), the graph is a tree; a drawing of a tree has one face, and \(V - (V - 1) + 1 = 2\). If \(E \ge V\), the graph contains a cycle. Let \(e\) be an edge on a cycle. The cycle is drawn as a closed curve without self-crossings, and by the Jordan curve theorem it separates the plane into an inside and an outside; the two sides of \(e\) therefore lie in different faces. Deleting \(e\) merges those two faces into one and keeps the graph connected, so the new drawing has \(V\) vertices, \(E - 1\) edges and \(F - 1\) faces. By induction \(V - (E - 1) + (F - 1) = 2\), which is the same as \(V - E + F = 2\).

Consequences. The number of faces does not depend on the drawing: every embedding of a connected planar graph has \(F = E - V + 2\) faces. If the graph has \(c\) components, applying the formula to each and noting that they share one outer face gives \(V - E + F = 1 + c\).

History. Euler stated the formula for convex polyhedra in letters of 1750 and published a proof in 1752, with vertices, edges and faces of the solid; projecting a convex polyhedron onto a plane from a point just outside one face gives a plane graph with the same counts. René Descartes had found an equivalent statement about angles around 1630, in a manuscript that was lost and rediscovered later. Augustin-Louis Cauchy gave the first proof in the graph-theoretic spirit in 1813. The quantity \(V - E + F\) is the Euler characteristic, which for a surface with \(g\) handles equals \(2 - 2g\); it was one of the first invariants of topology.

Planar graphs are sparse

Theorem. A simple planar graph with \(V \ge 3\) vertices has at most \(3V - 6\) edges. If it has no triangles, it has at most \(2V - 4\) edges.

Proof. It suffices to treat connected graphs, since adding edges between components keeps a graph planar. Every face of a simple graph with at least three vertices has degree at least 3: a face of degree 1 or 2 would need a loop or a multiple edge, unless the graph is a single edge. So \(2E = \sum\deg f \ge 3F\), that is, \(F \le 2E/3\). Euler's formula gives \(2 = V - E + F \le V - E + 2E/3\), so \(E \le 3V - 6\). If there are no triangles, every face has degree at least 4, so \(F \le E/2\) and \(E \le 2V - 4\).

Corollary. \(K_5\) and \(K_{3,3}\) are not planar. \(K_5\) has \(V = 5\) and \(E = 10 > 3 \cdot 5 - 6 = 9\). \(K_{3,3}\) is bipartite, so it has no odd cycles and in particular no triangles, and \(E = 9 > 2 \cdot 6 - 4 = 8\). The same reasoning with faces of degree at least 5 shows that the Petersen graph, whose shortest cycle has length 5, is not planar: a planar graph with girth \(g\) has \(E \le \frac{g}{g - 2}(V - 2)\), which is \(13\tfrac13\) for \(V = 10\), \(g = 5\), while the Petersen graph has 15 edges.

Minimum degree. Every simple planar graph has a vertex of degree at most 5. Otherwise \(2E = \sum\deg v \ge 6V\), so \(E \ge 3V > 3V - 6\). This small fact drives the proof of the six color theorem in lesson 9 and is the starting point of the proof of the four color theorem.

Average degree. Since \(E \le 3V - 6\), the average degree \(2E/V\) is less than 6. Planar graphs with many vertices are therefore always sparse, which is why algorithms on road networks and meshes run fast: storing them takes space proportional to \(V\).

The Platonic solids

A Platonic solid is a convex polyhedron whose faces are congruent regular polygons, with the same number of faces at every vertex. Let each face have \(p\) sides and each vertex have degree \(q\), with \(p, q \ge 3\). Then \(pF = 2E\) and \(qV = 2E\). Substituting into Euler's formula, \[\frac{2E}{q} - E + \frac{2E}{p} = 2, \qquad\text{so}\qquad \frac1p + \frac1q = \frac12 + \frac1E > \frac12.\] The only pairs \((p, q)\) with \(p, q \ge 3\) and \(\frac1p + \frac1q > \frac12\) are \((3, 3)\), \((3, 4)\), \((4, 3)\), \((3, 5)\) and \((5, 3)\), giving \(E = 6, 12, 12, 30, 30\): the tetrahedron, octahedron, cube, icosahedron and dodecahedron. Euclid's Elements ends with the construction of these five solids and an argument that there are no others; Euler's formula reduces that argument to arithmetic.

Duality

Given a plane drawing of a connected graph \(G\), its dual \(G^*\) has a vertex inside each face of \(G\), and for each edge \(e\) of \(G\) an edge \(e^*\) crossing \(e\) and joining the vertices of the two faces on either side of \(e\). The dual is planar, has \(F\) vertices, \(E\) edges and \(V\) faces, and the dual of the dual is \(G\) again. The cube and the octahedron are duals, as are the dodecahedron and the icosahedron, while the tetrahedron is its own dual. Duality exchanges cycles and cuts: a set of edges forms a cycle in \(G\) exactly when the dual edges form a minimal cut in \(G^*\). Coloring the faces of a map, as in the original four color problem, is the same as coloring the vertices of its dual, which is how map coloring becomes a question about graphs.

Kuratowski's theorem

Subdividing an edge means replacing it by a path through new vertices of degree 2. Subdivision does not change planarity. So any graph containing a subdivision of \(K_5\) or \(K_{3,3}\) is not planar. Remarkably, the converse holds.

Theorem (Kuratowski, 1930). A graph is planar if and only if it contains no subgraph that is a subdivision of \(K_5\) or of \(K_{3,3}\).

Kazimierz Kuratowski published the theorem in 1930; Orrin Frink and Paul Smith found it independently at about the same time but withdrew their paper. Klaus Wagner gave an equivalent form in 1937 in terms of minors: a graph is planar if and only if neither \(K_5\) nor \(K_{3,3}\) can be obtained from it by deleting and contracting edges. The proof is long and is not given here; it is the gateway to the graph minor theorem of Neil Robertson and Paul Seymour, proved in a series of twenty papers from 1983 to 2004, which says that every minor-closed family of graphs is characterized by a finite list of forbidden minors.

Applying the theorem. The Petersen graph contains a subdivision of \(K_{3,3}\), confirming that it is not planar. To show a graph is planar, it is usually easier to draw it. Planarity can be tested in linear time, by the algorithm of John Hopcroft and Robert Tarjan from 1974, and the test produces either an embedding or a Kuratowski subgraph as a certificate.

Straight lines suffice. Fáry's theorem, proved by István Fáry in 1948 and earlier by Wagner, says that every simple planar graph has a plane drawing in which every edge is a straight segment. Later work showed the vertices can be placed on a grid of size about \(2n \times n\), important for drawing networks on screens.

Crossings and other surfaces

For a nonplanar graph one can ask for the crossing number \(\mathrm{cr}(G)\), the fewest crossings in any drawing. Each crossing can be removed by deleting one edge, and a graph with \(E > 3V - 6\) must lose at least \(E - 3V + 6\) edges to become planar, so \(\mathrm{cr}(G) \ge E - 3V + 6\); in particular \(\mathrm{cr}(K_5) = 1\) and \(\mathrm{cr}(K_{3,3}) = 1\). A probabilistic sharpening, the crossing lemma of Ajtai, Chvátal, Newborn and Szemerédi and of Leighton (1982), gives \(\mathrm{cr}(G) \ge \frac{E^3}{64V^2}\) when \(E \ge 4V\). Paul Turán's brick factory problem from the Second World War, the crossing number of \(K_{m,n}\), is still open in general.

Graphs that cannot be drawn in the plane may fit on other surfaces. On a torus, \(V - E + F = 0\), and \(K_5\), \(K_{3,3}\) and even \(K_7\) can be drawn without crossings. The Euler characteristic bounds how dense a graph on a given surface can be, just as \(E \le 3V - 6\) does for the plane.

from itertools import combinations

def planar_edge_bound(V, E, girth=3):
    """Necessary condition from Euler's formula; True means the bound does not rule planarity out."""
    return E <= girth * (V - 2) / (girth - 2)

tests = {
    "K4": (4, 6, 3), "K5": (5, 10, 3), "K3,3": (6, 9, 4), "K2,5": (7, 10, 4),
    "Petersen": (10, 15, 5), "cube Q3": (8, 12, 4), "Q4": (16, 32, 4),
}
for name, (V, E, g) in tests.items():
    print(f"{name:9s} V={V:2d} E={E:2d} girth {g}: bound E <= {g * (V - 2) / (g - 2):5.2f} -> {'possible' if planar_edge_bound(V, E, g) else 'NOT planar'}")

def faces(rotation):
    """Trace faces of an embedding given by the cyclic order of adjacent vertices around each vertex."""
    darts = {(u, v) for u in rotation for v in rotation[u]}
    seen, result = set(), []
    for d in sorted(darts):
        if d in seen:
            continue
        face, (u, v) = [], d
        while (u, v) not in seen:
            seen.add((u, v)); face.append(u)
            nbrs = rotation[v]
            w = nbrs[(nbrs.index(u) - 1) % len(nbrs)]
            u, v = v, w
        result.append(face)
    return result

cube = {0: [1, 3, 4], 1: [2, 0, 5], 2: [3, 1, 6], 3: [0, 2, 7],
        4: [7, 5, 0], 5: [4, 6, 1], 6: [5, 7, 2], 7: [6, 4, 3]}
F = faces(cube)
V, E = len(cube), sum(len(x) for x in cube.values()) // 2
print("cube embedding faces:", F)
print("V - E + F =", V, "-", E, "+", len(F), "=", V - E + len(F), "; face degrees", [len(f) for f in F])

k4 = {0: [1, 2, 3], 1: [0, 3, 2], 2: [0, 1, 3], 3: [0, 2, 1]}
F4 = faces(k4)
print("K4 embedding: faces", len(F4), " V - E + F =", 4 - 6 + len(F4))

solids = []
for p in range(3, 20):
    for q in range(3, 20):
        s = 2 * p + 2 * q - p * q
        if s > 0 and (2 * p * q) % s == 0:
            E = 2 * p * q // s
            solids.append((p, q, 2 * E // q, E, 2 * E // p))
print("Platonic solutions (p, q, V, E, F):", solids)

def petersen_has_k33_subdivision():
    outer = [(i, (i + 1) % 5) for i in range(5)]
    inner = [(5 + i, 5 + (i + 2) % 5) for i in range(5)]
    spokes = [(i, i + 5) for i in range(5)]
    edges = outer + inner + spokes
    # delete two edges, smooth degree-2 vertices, and test whether K3,3 remains
    for drop in combinations(edges, 2):
        es = [e for e in edges if e not in drop]
        adj = {v: set() for v in range(10)}
        for a, b in es:
            adj[a].add(b); adj[b].add(a)
        changed = True
        while changed:
            changed = False
            for v in list(adj):
                if len(adj[v]) == 2:
                    a, b = adj[v]
                    if b in adj[a]:
                        continue
                    adj[a].discard(v); adj[b].discard(v); adj[a].add(b); adj[b].add(a); del adj[v]
                    changed = True
                    break
        if len(adj) == 6 and all(len(x) == 3 for x in adj.values()):
            side = {next(iter(adj))}
            for v in adj:
                if not adj[v] & side and v not in side and len(side) < 3 and all(v not in adj[s] for s in side):
                    side.add(v)
            if len(side) == 3 and all(adj[s] == set(adj) - side for s in side):
                return drop
    return None
print("Petersen: deleting edges", petersen_has_k33_subdivision(), "leaves a subdivided K3,3")

K4        V= 4 E= 6 girth 3: bound E <=  6.00 -> possible
K5        V= 5 E=10 girth 3: bound E <=  9.00 -> NOT planar
K3,3      V= 6 E= 9 girth 4: bound E <=  8.00 -> NOT planar
K2,5      V= 7 E=10 girth 4: bound E <= 10.00 -> possible
Petersen  V=10 E=15 girth 5: bound E <= 13.33 -> NOT planar
cube Q3   V= 8 E=12 girth 4: bound E <= 12.00 -> possible
Q4        V=16 E=32 girth 4: bound E <= 28.00 -> NOT planar
cube embedding faces: [[0, 1, 2, 3], [0, 3, 7, 4], [0, 4, 5, 1], [1, 5, 6, 2], [2, 6, 7, 3], [4, 7, 6, 5]]
V - E + F = 8 - 12 + 6 = 2 ; face degrees [4, 4, 4, 4, 4, 4]
K4 embedding: faces 4  V - E + F = 2
Platonic solutions (p, q, V, E, F): [(3, 3, 4, 6, 4), (3, 4, 6, 12, 8), (3, 5, 12, 30, 20), (4, 3, 8, 12, 6), (5, 3, 20, 30, 12)]
Petersen: deleting edges ((0, 1), (7, 9)) leaves a subdivided K3,3

The edge bound rules out \(K_5\) and \(K_{3,3}\), while \(K_{2,5}\) passes the test and is indeed planar; the Petersen graph and the four-dimensional cube \(Q_4\) are ruled out by the girth version. Tracing faces from the cyclic order of neighbors, a rotation system, confirms \(V - E + F = 2\) for the cube and for \(K_4\). The search over \((p, q)\) finds exactly the five Platonic solids, and deleting two edges from the Petersen graph and smoothing vertices of degree 2 leaves \(K_{3,3}\), a Kuratowski certificate of nonplanarity.