Chapter 26 of 30

Planar Graphs

Can you connect three houses to three utilities (water, gas, electricity) with pipes that never cross? Can a circuit board route its wires on a single layer without two tracks touching? Both puzzles ask the same question: can this graph be drawn on a flat sheet without edge crossings? Graphs that can are called planar graphs.

Planarity is one of the most elegant parts of graph theory. A single equation, Euler's formula v − e + f = 2, gives us strong limits on how many edges a planar graph can have, lets us prove that K5 and K3,3 are not planar, and even explains why there are only five Platonic solids. In this chapter we build on the vocabulary of Graph Theory Basics (vertices, edges, degree, cycles, Kn, Km,n) and the idea of isomorphism from Graph Representations & Isomorphism.

A graph is planar if it can be drawn in the plane so that edges meet only at their common endpoints. Such a drawing is called a plane graph (or planar embedding). The drawing divides the plane into regions called faces.


Planar Graph vs Plane Drawing

Planarity is a property of the graph, not of one particular picture. A graph is planar if some drawing has no crossings, even if the drawing you were given has crossings everywhere.

The classic example is K4. The usual "square with both diagonals" picture has one crossing, but pulling one diagonal outside the square removes it:

  Drawing with a crossing          Crossing-free drawing of the same K4

    a ─────── b                                a
    │ ╲     ╱ │                               ╱│╲
    │   ╲ ╱   │                              ╱ │ ╲
    │   ╱ ╲   │                             ╱  d  ╲
    │ ╱     ╲ │                            ╱ ╱   ╲ ╲
    c ─────── d                           b ─────── c

  Not a plane drawing                    K4 IS planar (d sits inside triangle abc)

Both pictures have the same 4 vertices and the same 6 edges; only the positions changed.

Faces

A plane drawing cuts the plane into connected regions called faces (or regions). Exactly one face is unbounded: the outer face. The crossing-free K4 has 4 faces: the three small triangles around d, plus the outer face.

The degree of a face is the number of edges on its boundary walk, where an edge that has the same face on both sides (a bridge) is counted twice.

Each edge either separates two faces or appears twice on the boundary of one face. Either way it contributes exactly 2 to the total, which gives the face version of the handshaking lemma:

Face handshaking lemma: in any plane graph, the sum of the degrees of all faces = 2e.

Example: a path a – b – c drawn in the plane has one face (the outer face), and its boundary walk is a, b, c, b, a, of length 4 = 2 × 2 edges. Each bridge is counted twice.


Euler's Formula

Euler's formula: if G is a connected plane graph with v vertices, e edges and f faces, then v − e + f = 2.

Quick checks:

Graph

v

e

f

v − e + f

Any tree on n vertices

n

n − 1

1

2

Cycle Cn

n

n

2 (inside, outside)

2

K4

4

6

4

2

Cube graph Q3

8

12

6

2

Pentagonal prism

10

15

7

2

Proof (induction on the number of edges)

Let G be a connected plane graph. We use strong induction on e.

  • Case 1: G has no cycle. (A connected graph with no cycle is called a tree; trees get their own chapter later.) Then e = v − 1. Reason: if v ≥ 2, take a longest path; its end vertex has degree 1, since any other neighbour would either extend the path or close a cycle. Deleting that vertex and its edge leaves a smaller connected graph with no cycle, so repeating this until one vertex is left removes exactly one edge per vertex removed. A drawing with no cycle encloses no region, so f = 1. Then v − e + f = v − (v − 1) + 1 = 2.

  • Case 2: G has a cycle C. Pick any edge x on C. Removing an edge of a cycle keeps the graph connected (the rest of the cycle is a detour). In the drawing, C is a closed curve, so by the Jordan curve theorem the faces on the two sides of x are different: one is inside C and one is outside. Deleting x merges these two faces into one. The new plane graph G − x is connected, has v vertices, e − 1 edges and f − 1 faces. By the induction hypothesis v − (e − 1) + (f − 1) = 2, which simplifies to v − e + f = 2. ∎

Since the formula fixes f = e − v + 2, every plane drawing of a connected planar graph has the same number of faces, even though the faces may look different.

Disconnected graphs

If G has k connected components, add k − 1 edges to join them (this creates no new faces), apply Euler's formula, and subtract again. The result is:

For a plane graph with k components: v − e + f = k + 1.

Worked example 1

A connected planar graph has 10 vertices, each of degree 3. How many faces does any plane drawing have?

By the handshaking lemma, 2e = 10 × 3 = 30, so e = 15. Then f = e − v + 2 = 15 − 10 + 2 = 7. (The pentagonal prism is such a graph: 2 pentagons + 5 squares = 7 faces.)

Worked example 2

A connected plane graph has 6 vertices and every face (including the outer one) is a triangle. Find e and f.

Every face has degree 3, so by face handshaking 3f = 2e. Euler: 6 − e + f = 2, so f = e − 4. Substituting: 3(e − 4) = 2e, so e = 12, f = 8. This is the octahedron.


Edge Bounds: The Main Corollaries

Euler's formula becomes a powerful non-planarity test once we combine it with face degrees.

Corollary 1. If G is a simple connected planar graph with v ≥ 3, then e ≤ 3v − 6.

Proof. If G has no cycle, e = v − 1 ≤ 3v − 6 because v ≥ 3. Otherwise G has a cycle, and in a simple graph every face boundary then has length at least 3: a face of degree 1 would need a loop, and a face of degree 2 would need two parallel edges (or the whole graph would be a single edge, which has no cycle). So 2e = Σ deg(face) ≥ 3f, that is f ≤ 2e/3. Then 2 = v − e + f ≤ v − e + 2e/3 = v − e/3, so e ≤ 3v − 6. ∎

Corollary 2. If G is simple, connected, planar, v ≥ 3, and has no triangles (cycles of length 3), then e ≤ 2v − 4.

Proof. A graph with no cycle has e = v − 1 ≤ 2v − 4 for v ≥ 3. Otherwise, as in Corollary 1, every face has degree at least 3, and a face of degree exactly 3 would be bounded by a closed walk of length 3, which in a simple graph is a triangle. With no triangles every face has degree at least 4, so 2e ≥ 4f, f ≤ e/2, and 2 ≤ v − e + e/2, giving e ≤ 2v − 4. ∎

The general version: if every cycle has length at least g (the girth) and G contains a cycle, then 2e ≥ gf, and the same algebra gives

Corollary 3. If G is simple, connected, planar, contains at least one cycle, and every cycle has length at least g (g ≥ 3), then e ≤ g(v − 2)/(g − 2). (g = 3 gives 3v − 6, g = 4 gives 2v − 4.)

Corollary 4. Every simple planar graph has a vertex of degree at most 5.

Proof. It is enough to check each component, so assume G is connected. If v ≤ 2 it is obvious. Otherwise, if every vertex had degree ≥ 6, then 2e = Σ deg(v) ≥ 6v, so e ≥ 3v, contradicting e ≤ 3v − 6. ∎ This tiny fact is the engine behind coloring proofs in Graph Coloring.


K5 and K3,3 Are Not Planar

K5: v = 5, e = C(5, 2) = 10. Corollary 1 allows at most 3·5 − 6 = 9 edges. Since 10 > 9, K5 is not planar.

K3,3 (the utilities puzzle): v = 6, e = 9. Corollary 1 allows 12 edges, so it gives no conclusion. But K3,3 is bipartite, and a bipartite graph has no odd cycles, in particular no triangles. Corollary 2 allows at most 2·6 − 4 = 8 edges. Since 9 > 8, K3,3 is not planar. So the three houses cannot be connected to three utilities without a crossing.

Petersen graph: v = 10, e = 15, girth 5. Corollary 3 allows at most 5·8/3 ≈ 13.3, so at most 13 edges. Since 15 > 13, it is not planar. (Corollary 1 would allow 24 and Corollary 2 would allow 16, so you really need the girth version here.)

The bounds are one-way tests. Breaking a bound proves non-planarity. Satisfying a bound proves nothing: K3,3 satisfies e ≤ 3v − 6 and still is not planar.

Which standard families are planar?

Family

Planar exactly when

Smallest non-planar member and reason

Complete graph Kn

n ≤ 4

K5: 10 > 3·5 − 6

Complete bipartite Km,n (m ≤ n)

m ≤ 2

K3,3: 9 > 2·6 − 4

Hypercube Qn

n ≤ 3

Q4: 32 > 2·16 − 4 = 28 (bipartite)

Trees, cycles, wheels

always

none

K2,n is planar for every n: put the two special vertices at the top and bottom and the n others in a horizontal row between them.


Kuratowski's Theorem

K5 and K3,3 turn out to be the only two "obstacles" to planarity. To state this precisely we need one definition.

A subdivision of a graph H is obtained by replacing edges of H with paths (inserting new degree-2 vertices in the middle of edges).

Inserting a vertex in the middle of an edge clearly does not change whether a graph can be drawn without crossings. So a subdivision of K5 or K3,3 is non-planar, and so is any graph that contains one as a subgraph.

Kuratowski's theorem (1930): a graph is planar if and only if it contains no subgraph that is a subdivision of K5 or of K3,3.

The "only if" direction is the easy observation above; the "if" direction is the deep part. A closely related version is Wagner's theorem: G is planar if and only if neither K5 nor K3,3 can be obtained from G by deleting vertices or edges and contracting edges (they are not minors of G).

The Petersen graph shows why the two versions differ. Contracting the five "spoke" edges (outer vertex i joined to inner vertex i) turns it into K5, so K5 is a minor. But Petersen has maximum degree 3, so it cannot contain a subdivision of K5 (which needs five vertices of degree 4). It does contain a subdivision of K3,3, which is what Kuratowski's theorem promises.

In practice, planarity is tested by linear-time algorithms (Hopcroft and Tarjan, 1974, and later simpler ones), which is what circuit-layout software uses.


Special Planar Graphs

Maximal planar graphs (triangulations)

A simple planar graph is maximal planar if adding any new edge destroys planarity. For v ≥ 3, in any plane drawing every face is a triangle, so 3f = 2e exactly, and the bounds become equalities:

Maximal planar, v ≥ 3: e = 3v − 6 and f = 2v − 4.

For example, a maximal planar graph on 20 vertices has 54 edges and 36 faces, and 54 is the maximum number of edges any simple planar graph on 20 vertices can have.

The dual graph

Given a connected plane graph G, its dual G* has one vertex for each face of G, and for each edge e of G, an edge of G* joining the faces on the two sides of e (a loop if the same face is on both sides). Then:

  • v(G*) = f(G), e(G*) = e(G), f(G*) = v(G).

  • The degree of a vertex in G* equals the degree of the corresponding face in G.

  • The cube and the octahedron are duals of each other; the tetrahedron (K4) is its own dual.

Duality turns face coloring of a map into vertex coloring of a graph, which is how the Four Color Theorem in Graph Coloring is usually stated.

Why there are only five Platonic solids

A Platonic solid has every face a regular p-gon and every vertex of degree q, with p, q ≥ 3. Its edges form a connected planar graph, so 2e = pf = qv. Substituting v = 2e/q and f = 2e/p into Euler's formula:

2e/q − e + 2e/p = 2      ⟹      1/p + 1/q = 1/2 + 1/e  > 1/2

With p, q ≥ 3 this forces (p, q) to be one of only five pairs:

(p, q)

Solid

v

e

f

(3, 3)

Tetrahedron

4

6

4

(4, 3)

Cube

8

12

6

(3, 4)

Octahedron

6

12

8

(5, 3)

Dodecahedron

20

30

12

(3, 5)

Icosahedron

12

30

20

Notice that swapping p and q swaps v and f: that is exactly duality.


Checking with Code

This program applies the girth bound to several graphs and then derives the Platonic solids from Euler's formula. It uses only standard Python.

def edge_bound(v, girth):
    """Max edges of a simple connected planar graph with v >= 3 vertices
    whose shortest cycle has length >= girth (girth 3 = no restriction)."""
    return girth * (v - 2) // (girth - 2)

graphs = [  # name, vertices, edges, girth
    ("K4",            4,  6, 3),
    ("K5",            5, 10, 3),
    ("K3,3",          6,  9, 4),
    ("Petersen",     10, 15, 5),
    ("Q3 (cube)",     8, 12, 4),
    ("Q4",           16, 32, 4),
]
for name, v, e, g in graphs:
    limit = edge_bound(v, g)
    verdict = "NOT planar (bound broken)" if e > limit else "test passes (no conclusion)"
    print(f"{name:10} v={v:2} e={e:2} girth={g}  bound={limit:2}  {verdict}")

print("\nRegular polyhedra from Euler's formula:")
# every face has p sides, every vertex has degree q:  2e = p*f = q*v
for p in range(3, 10):
    for q in range(3, 10):
        # v - e + f = 2  with v = 2e/q, f = 2e/p  gives  e = 2pq / (2p + 2q - pq)
        d = 2 * p + 2 * q - p * q
        if d > 0:
            e = 2 * p * q // d
            print(f"faces are {p}-gons, degree {q}:  v={2*e//q:2} e={e:2} f={2*e//p:2}")

Output:

K4         v= 4 e= 6 girth=3  bound= 6  test passes (no conclusion)
K5         v= 5 e=10 girth=3  bound= 9  NOT planar (bound broken)
K3,3       v= 6 e= 9 girth=4  bound= 8  NOT planar (bound broken)
Petersen   v=10 e=15 girth=5  bound=13  NOT planar (bound broken)
Q3 (cube)  v= 8 e=12 girth=4  bound=12  test passes (no conclusion)
Q4         v=16 e=32 girth=4  bound=28  NOT planar (bound broken)

Regular polyhedra from Euler's formula:
faces are 3-gons, degree 3:  v= 4 e= 6 f= 4
faces are 3-gons, degree 4:  v= 6 e=12 f= 8
faces are 3-gons, degree 5:  v=12 e=30 f=20
faces are 4-gons, degree 3:  v= 8 e=12 f= 6
faces are 5-gons, degree 3:  v=20 e=30 f=12

"Test passes" for K4 and Q3 is consistent with them being planar, but notice the program never claims planarity: a passed bound is not a proof.


Common Mistakes

  • Judging planarity from one drawing. Crossings in a given picture prove nothing; you must show that no drawing avoids them.

  • Using e ≤ 3v − 6 as a planarity proof. It is only a necessary condition. K3,3 satisfies it and is non-planar.

  • Applying e ≤ 2v − 4 to graphs with triangles. It needs triangle-free graphs (for example, bipartite ones).

  • Forgetting the outer face. A cycle has 2 faces, not 1. A tree has exactly 1.

  • Using v − e + f = 2 for disconnected graphs. With k components it is v − e + f = k + 1.

  • Applying the bounds to multigraphs. With loops or parallel edges, faces can have degree 1 or 2 and the inequalities fail.


Practice and GATE-Style Questions

Q1. A connected planar graph has 20 vertices, each of degree 3. How many regions does a planar drawing have?

2e = 20 × 3 = 60, so e = 30. f = e − v + 2 = 30 − 20 + 2 = 12. (The dodecahedron is an example.)

Q2. What is the maximum number of edges in a simple planar graph with 12 vertices? With 12 vertices and no triangles?

3·12 − 6 = 30 (achieved by the icosahedron, which is maximal planar). Without triangles: 2·12 − 4 = 20.

Q3. A planar graph has 3 connected components, 15 vertices and 20 edges. How many faces?

v − e + f = k + 1 gives 15 − 20 + f = 4, so f = 9.

Q4. Is K5 minus one edge planar? Is K3,3 minus one edge planar?

Both are planar. K5 − e has 9 = 3·5 − 6 edges and is in fact maximal planar. K3,3 − e has 8 = 2·6 − 4 edges. The bounds alone only allow planarity; to prove it, draw them. For K5 − ab: draw the triangle cde, put a inside it and b outside it, and join each of a and b to c, d and e. For K3,3 − a1b1: draw the hexagon a1 b2 a2 b1 a3 b3 (back to a1); the two remaining edges a2b3 and a3b2 go one inside and one outside the hexagon.

Q5. Prove that a simple connected planar graph with fewer than 12 vertices has a vertex of degree at most 4.

Suppose every vertex has degree ≥ 5. Then 2e ≥ 5v. Combined with e ≤ 3v − 6: 5v/2 ≤ 3v − 6, so v ≥ 12. Contradiction with v < 12. (The bound is tight: the icosahedron has 12 vertices, all of degree 5.)

Q6. Every face of a connected plane graph has degree 4 and the graph has 16 edges. How many vertices?

4f = 2e = 32, so f = 8. Then v = e − f + 2 = 16 − 8 + 2 = 10.


Summary

  • A graph is planar if some drawing has no crossings; a crossing-free drawing has faces, including one outer face.

  • Sum of face degrees = 2e. Euler: v − e + f = 2 for connected plane graphs, k + 1 for k components.

  • Simple, connected, v ≥ 3: e ≤ 3v − 6; triangle-free: e ≤ 2v − 4; girth g: e ≤ g(v − 2)/(g − 2). Every simple planar graph has a vertex of degree ≤ 5.

  • K5 and K3,3 are non-planar, and by Kuratowski's theorem their subdivisions are the only obstacles.

  • Maximal planar graphs have exactly 3v − 6 edges and 2v − 4 faces; duals swap vertices and faces; Euler's formula allows only five Platonic solids.

Euler's formula turns a geometric question (can it be drawn flat?) into simple arithmetic on v, e and f. When the arithmetic breaks, the graph cannot be planar.