Discrete Math › Section C · Graph theory › Topic C.4

Planar graphs

Can a circuit be printed on a board without any wires crossing? Can three houses each be piped to three utilities without pipes crossing? Questions like these ask whether a graph is planar, and one short formula of Euler's answers many of them.

Drawings without crossings

A graph is planar if it can be drawn in the plane with no two edges crossing; such a drawing is a plane drawing. The word "can" matters. The usual picture of \(K_4\), a square with both diagonals, has a crossing, yet \(K_4\) is planar: draw the square, keep one diagonal inside, and route the other diagonal around the outside. So one drawing with crossings proves nothing. To show a graph is planar, produce a plane drawing. To show it is not, you need an argument that every possible drawing has a crossing.

Faces

A plane drawing cuts the plane into regions called faces. One face is unbounded: the outer face, everything outside the drawing. It counts like any other. A tree has just one face, since it encloses nothing. A cycle \(C_n\) has two faces, inside and outside. The plane drawing of \(K_4\) described above has four faces: three triangles that you can see as bounded regions, plus the outer face, which is also bounded by a triangle. Each face has a boundary made of edges, and every edge lies on the boundary of one or two faces.

Euler's formula

For any connected graph drawn in the plane without crossings, with \(v\) vertices, \(e\) edges and \(f\) faces,

v - e + f = 2

The number of faces is therefore the same for every plane drawing of the graph, even though the drawings may look very different. Check it on \(K_4\): \(4 - 6 + 4 = 2\). On a cycle \(C_n\): \(n - n + 2 = 2\). On a tree: \(v - (v - 1) + 1 = 2\). For a graph with \(c\) components the formula becomes \(v - e + f = 1 + c\), so connectedness is part of the statement.

Why Euler's formula holds

Start from a spanning tree of the connected plane graph, which exists by the previous topic. The tree has \(v\) vertices, \(v - 1\) edges and one face, so \(v - e + f = 2\) is true for it. Now put back the missing edges one at a time. Each one joins two vertices already connected through the tree, so it closes a cycle and splits one face into two. Each step raises \(e\) by 1 and \(f\) by 1, leaving \(v - e + f\) unchanged. When every edge is back, the original graph still satisfies \(v - e + f = 2\).

Worked example: using the formula

1. A cube's corners and edges form a planar graph with 8 vertices and 12 edges, so \(f = 2 - 8 + 12 = 6\): five visible squares and the outer face, matching the cube's 6 faces. 2. A connected planar graph has 10 vertices, each of degree 3. By the handshake lemma \(2e = 30\), so \(e = 15\), and any plane drawing has \(f = 2 - 10 + 15 = 7\) faces. 3. A triangular prism has 6 vertices and 9 edges, so it has \(2 - 6 + 9 = 5\) faces: two triangles and three rectangles. In each case, counting the outer face is what makes the answer match.

Too many edges to be planar

Suppose a simple connected planar graph has at least 3 vertices. Walk around each face and count the edges on its boundary: each face needs at least 3, and each edge is counted at most twice, once from each side. So \(3f \le 2e\). Substituting \(f = 2 - v + e\) from Euler's formula and simplifying gives

e \le 3v - 6

If the graph has no triangles, as in any bipartite graph, each face needs at least 4 edges, so \(4f \le 2e\), which leads to \(e \le 2v - 4\). A graph that breaks either bound cannot be planar.

Worked example: K5 and K3,3

1. \(K_5\) has \(v = 5\) and \(e = 10\). The bound allows at most \(3 \cdot 5 - 6 = 9\) edges, and 10 is more, so \(K_5\) is not planar. 2. \(K_{3,3}\) has \(v = 6\) and \(e = 9\). The first bound allows 12, so it settles nothing. But \(K_{3,3}\) is bipartite, so it has no triangles, and the second bound allows at most \(2 \cdot 6 - 4 = 8\) edges. Nine is more, so \(K_{3,3}\) is not planar. 3. This is the three-utilities puzzle: houses on one side, utilities on the other, an edge for each pipe. It cannot be done in the plane.

Kuratowski's theorem

These two graphs are the essential obstacles. Subdividing an edge means replacing it with a path through new vertices of degree 2, which changes nothing about crossings. Kuratowski's theorem, proved in 1930, says a graph is planar if and only if it contains no subgraph that is a subdivision of \(K_5\) or of \(K_{3,3}\). Keep the logic of the edge bounds straight: breaking a bound proves a graph is non-planar, but meeting a bound proves nothing, as \(K_{3,3}\) showed when it passed the first bound.

Worked example: why a football has 12 pentagons

Picture a football (a soccer ball) stitched from pentagons and hexagons, with three panels meeting at every corner. Let \(p\) and \(h\) be the numbers of each. 1. Faces: \(f = p + h\). 2. Each edge borders two panels: \(e = (5p + 6h)/2\). 3. Each corner touches three panels: \(v = (5p + 6h)/3\). 4. Substitute into \(v - e + f = 2\) and multiply by 6:

10p + 12h - 15p - 18h + 6p + 6h = 12

which simplifies to \(p = 12\). The number of hexagons is not fixed, but there are always exactly 12 pentagons. The classic ball, with 20 hexagons, has \(60 - 90 + 32 = 2\).

Polyhedra and the five regular solids

The corners and edges of a convex polyhedron form a connected planar graph: imagine looking through one face and flattening the rest inside it. So Euler's formula holds for every convex polyhedron. A regular polyhedron has identical regular polygons for faces, with the same number meeting at each corner. Arguments like the football one show that there are exactly five: the tetrahedron (4 vertices, 6 edges, 4 faces), cube (8, 12, 6), octahedron (6, 12, 8), dodecahedron (20, 30, 12) and icosahedron (12, 30, 20). Each satisfies \(v - e + f = 2\).

Common mistakes to avoid

First, forgetting the outer face, which makes every face count one too small. Second, deciding a graph is not planar because one drawing has crossings; try to redraw it. Third, believing that a graph meeting \(e \le 3v - 6\) must be planar; the bound only rules graphs out. Fourth, using \(e \le 2v - 4\) on a graph that contains triangles, where it does not apply. Fifth, applying \(v - e + f = 2\) to a disconnected graph.

Key takeaways

A graph is planar if some drawing of it has no crossings, and a plane drawing divides the plane into faces, including the outer face. Euler's formula, \(v - e + f = 2\), holds for every connected plane graph and every convex polyhedron. For simple connected planar graphs with at least 3 vertices, \(e \le 3v - 6\), and \(e \le 2v - 4\) when there are no triangles. These bounds show \(K_5\) and \(K_{3,3}\) are not planar, and Kuratowski's theorem says those two are the only fundamental obstacles.

Flashcards

Flashcard

Planar graph

A graph that can be drawn with no edges crossing

One crossing drawing proves nothing.

Test your understanding

Question 1 of 5

A connected planar graph has 12 vertices and 18 edges. How many faces does any plane drawing of it have?

Question 2 of 5

A simple connected planar graph has 8 vertices. What is the largest number of edges it can have?

Question 3 of 5

A convex polyhedron has 14 vertices and 21 edges. How many faces does it have?

Question 4 of 5

K₃,₃ has 6 vertices and 9 edges, and 9 ≤ 3 × 6 − 6. What follows from this alone?

Question 5 of 5

Someone draws a graph and two of its edges cross. What can you conclude?

← Previous topicNext topic →