Planarity and colouring

Some graphs can be drawn on paper with no two edges crossing and some cannot, and the problem is to tell which is which, then to find how few colours are needed so that neighbouring regions of a map never share one.

The previous lesson proved that a tree, a connected graph with no cycles, on $V$ vertices has exactly $V-1$ edges, and that every connected graph contains a spanning tree, a tree using all of its vertices and some of its edges. Both facts are used below. Graphs here are simple (no loops, no repeated edges), $K_n$ is the complete graph on $n$ vertices, and $K_{m,n}$ joins each of $m$ vertices to each of $n$ others. So far a graph has been pure combinatorics, a list of what is joined to what. The question now is geometric, and the answer starts from a formula Euler sent to Christian Goldbach in 1750.

Drawings, faces and the outer face

A plane drawing of a graph puts each vertex at a point and each edge along a curve between its ends, so that curves meet only at shared ends. A graph is planar if it has a plane drawing, and a graph together with one is a plane graph. $K_4$ drawn as a square with both diagonals has a crossing, but moving one vertex inside the triangle of the other three removes it, so $K_4$ is planar although that first drawing is not a plane one.

A plane drawing cuts the rest of the plane into regions called faces. Exactly one is unbounded, the outer face, surrounding the whole drawing. The cycle $C_4$ has two faces, inside and outside. $K_4$ with one vertex in the middle has four: three small triangles and the outer face. A tree has only one, since no cycle encloses anything.

The degree of a face is the length of the walk around its boundary, and an edge with the same face on both sides, such as every edge of a tree, is walked twice and counts twice. Then every edge contributes exactly $2$, one for each side, so the face degrees of a plane graph add up to $2E$. It is the handshake lemma again, counting edge and face incidences instead of edge and vertex ones.

Polyhedra supply plane graphs. Puncture one face of a convex polyhedron and stretch the surface flat through the hole: the vertices and edges become a plane graph, and the punctured face becomes the outer face. The cube becomes a small square inside a large one with corners joined: $8$ vertices, $12$ edges and $6$ faces.

Euler's formula

Theorem (Euler). A connected plane graph with $V$ vertices, $E$ edges and $F$ faces has $V-E+F=2$.

The proof is by induction on the number of edges outside a spanning tree. Let $T$ be a spanning tree of the connected plane graph $G$, drawn as it sits inside $G$. It has $V-1$ edges and one face, so for $T$ the count is $V-(V-1)+1=2$. Now put the other edges of $G$ back one at a time. Each new edge $\{u,v\}$ joins two vertices already connected by a path in the tree, so it closes a cycle, a closed curve separating the plane into an inside and an outside. The face the new edge runs through is cut in two and no other face changes. Each step adds one edge and one face, so $V-E+F$ stays $2$, and when every edge is back the graph is $G$.

That a closed curve without self-crossings splits the plane into exactly two regions is the Jordan curve theorem. It looks obvious and is hard to prove for arbitrary curves (Camille Jordan's 1887 proof was later judged incomplete), but for curves made of straight segments, which is all a drawing needs, it is elementary, and here it is taken on trust.

The cube has $8-12+6=2$. The dodecahedron has $12$ pentagonal faces; each edge lies on $2$ of them, so $E=\frac{12\times 5}{2}=30$, and each vertex on $3$, so $V=\frac{12\times 5}{3}=20$. Then $20-30+12=2$. Connectedness matters: two separate triangles have $6-6+3=3$, and in general a plane graph with $c$ components has $V-E+F=1+c$.

Example. A connected plane graph has every vertex of degree $3$, and every face is a pentagon or a hexagon. Show that it has exactly $12$ pentagons, however many hexagons it has.

Let there be $p$ pentagons and $h$ hexagons, so $F=p+h$. Face degrees sum to $2E$, so $2E=5p+6h$, and vertex degrees sum to $2E$, so $3V=2E$. Multiply Euler's formula by $6$ and substitute $6V=4E$ to get $6F-2E=12$, that is $6p+6h-5p-6h=12$, so $p=12$. The hexagons cancel. The dodecahedron is the case $h=0$, and a football, $12$ pentagons and $20$ hexagons, has $E=\frac{60+120}{2}=90$ and $V=60$, with $60-90+32=2$.

Now you. A connected plane graph has every vertex of degree $3$, and every face is a square or a hexagon. How many squares does it have?

Too many edges to be planar

Theorem. A simple planar graph with $V\ge 3$ vertices has $E\le 3V-6$.

Take a plane drawing, and suppose first it is connected. A face of degree $1$ or $2$ would need a loop, a repeated edge, or a graph that is a single edge, all ruled out. So every face has degree at least $3$, and counting edge and face incidences gives $2E\ge 3F$. Euler's formula with $F\le \frac{2E}{3}$ gives $2=V-E+F\le V-\frac{E}{3}$, which rearranges to $E\le 3V-6$. A disconnected planar graph can have edges added between components, staying planar, until it is connected, and the bound for the larger graph covers the smaller.

$K_5$ has $V=5$ and $E=10$, while $3V-6=9$. So $K_5$ is not planar: five towns each joined directly to every other cannot have their roads laid flat without a crossing.

If a graph has no triangles, every face has degree at least $4$, so $2E\ge 4F$ and the same algebra gives $E\le 2V-4$. The graph $K_{3,3}$ has no triangles, since every edge crosses between the sides and so every cycle is even. It has $V=6$ and $E=9>8$, so it is not planar. This is the three utilities puzzle: three houses each to be joined to gas, water and electricity with no two pipes crossing, which cannot be done. Notice that $K_{3,3}$ passes the first test, $9\le 12$: the bounds are necessary conditions only.

Example. Show that for every simple graph $G$ on $11$ vertices, $G$ or its complement (same vertices, joined exactly where $G$ has no edge) is not planar.

Between them $G$ and its complement contain every pair once, so their edges number $\left(\genfrac{}{}{0ex}{}{11}{2}\right)=55$. If both were planar each would have at most $3\times 11-6=27$ edges, $54$ in all. Since $55>54$, one of them has at least $28$ edges and is not planar.

Now you. The Petersen graph has as vertices the ten two element subsets of $\{1,2,3,4,5\}$, two joined when they are disjoint. Every vertex has degree $3$, and its shortest cycle has length $5$. Show that it is not planar, although it satisfies both bounds above.

Subdividing an edge, replacing it by a path through new vertices of degree $2$, changes no picture, so a graph containing a subdivided $K_5$ or $K_{3,3}$ is not planar. Kazimierz Kuratowski proved in 1930 that these are the only obstructions.

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

The hard direction, that a graph avoiding both can always be drawn, is beyond this course. The Petersen graph contains a subdivided $K_{3,3}$, as it must.

Colourings and the chromatic number

A proper colouring gives each vertex a colour so that adjacent vertices differ, and the chromatic number $\chi (G)$ is the fewest colours that allow one. $K_n$ needs $n$. An even cycle alternates two colours; an odd cycle cannot, since alternating around it brings the start back with the wrong colour, so $\chi (C_n)=3$ for odd $n$. Showing $\chi (G)=k$ takes two halves: a colouring with $k$ colours, and a reason $k-1$ fail.

Maps become graphs through their dual: a vertex inside each country, two joined when they share a stretch of border, not just a point. Each dual edge crosses only the border it stands for, so the dual of a map is planar, and colouring countries so that neighbours differ is properly colouring the vertices of a planar graph.

The same idea schedules. Make each exam a vertex and join two when some student sits both. A proper colouring assigns time slots with no student in two rooms at once, and $\chi$ is the fewest slots possible.

Example. Six exams $A,B,C,D,E,F$ have clashes $AB$, $BC$, $CD$, $DE$, $EA$, $FA$ and $FC$. How many slots are needed?

$A,B,C,D,E$ form a cycle of length $5$, which is odd, so at least $3$. Three suffice: $A$ and $C$ in slot $1$, $B$ and $D$ in slot $2$, $E$ in slot $3$, and $F$, whose clashes $A$ and $C$ are both in slot $1$, in slot $2$. Every clashing pair is split: $AB$ is $1,2$; $BC$ is $2,1$; $CD$ is $1,2$; $DE$ is $2,3$; $EA$ is $3,1$; $FA$ and $FC$ are $2,1$. So $\chi =3$.

Now you. A seventh exam $G$ clashes with each of $A,B,C,D$ and $E$. How many slots are needed now?

No efficient method is known for the chromatic number in general. Computing it was among the problems Richard Karp showed NP-complete in 1972, the same class as the Hamilton cycle question, and even deciding whether $3$ colours suffice is that hard.

Two colours and odd cycles

Two colours, by contrast, are completely understood. A graph is bipartite if its vertices split into two sides with every edge crossing between them, which is the same thing as a proper colouring with two colours.

Theorem. A graph is two colourable if and only if it has no cycle of odd length.

If it is two colourable, colours alternate around any cycle, so returning to the start takes an even number of steps.

Conversely, suppose there is no odd cycle, and treat each connected component separately. Take a spanning tree, choose a root $r$, and colour each vertex by the parity of its depth $d$, its distance from $r$ along the tree. Tree edges join consecutive depths, so they are fine. Suppose another edge $\{u,v\}$ joined two vertices of the same colour, and let $w$ be the last vertex shared by the tree paths from $r$ to $u$ and to $v$. The tree path from $u$ to $v$ through $w$ has length $d(u)+d(v)-2d(w)$, which is even because $d(u)$ and $d(v)$ have the same parity. Adding $\{u,v\}$ closes a cycle of odd length, a contradiction.

The proof is also an algorithm: colour by depth, and either every edge checks out or a clashing edge exhibits an odd cycle. Two colours are decided quickly; three is the hard problem.

Six colours suffice

Lemma. Every simple planar graph has a vertex of degree at most $5$.

With $V\le 2$ this is clear. Otherwise the degrees sum to $2E\le 6V-12$, so the average degree is below $6$, and some vertex is at or below the average.

Theorem. Every planar graph can be properly coloured with $6$ colours.

By induction on $V$. A graph with at most $6$ vertices gets a different colour on each. For larger $G$, delete a vertex $v$ of degree at most $5$. What remains is planar, so by induction it has a $6$ colouring. The neighbours of $v$ use at most $5$ colours, so a sixth is free for $v$.

Alfred Kempe published a proof in 1879 that four colours suffice, handling a $v$ of degree $4$ or $5$ by swapping colours along two coloured chains of vertices to free one up. It stood for eleven years until Percy Heawood found, in 1890, a case the swaps miss. Heawood salvaged what Kempe's chains do prove, the five colour theorem.

Four colours and a proof by computer

In 1852 Francis Guthrie, colouring a map of the counties of England, noticed that four colours were enough and asked whether that was always so. His brother Frederick passed the question to Augustus De Morgan, who wrote of it to William Rowan Hamilton that October. Four cannot be lowered, since $K_4$ is planar and needs four.

Theorem (four colour theorem). Every planar graph can be properly coloured with $4$ colours.

Kenneth Appel and Wolfgang Haken at the University of Illinois proved it in 1976. By hand they showed that a smallest counterexample would have to contain one of almost two thousand configurations. A computer then checked that none of them can occur in a smallest counterexample, which took about 1,200 hours of machine time, and no person has checked that part through. Neil Robertson, Daniel Sanders, Paul Seymour and Robin Thomas gave a simpler proof in 1997 with $633$ configurations, and in 2005 Georges Gonthier checked the whole argument in the Coq proof assistant, a program that verifies every logical step down to the axioms.

A proof is an argument that each step follows from the last, and nothing requires the checker to be human. The worry in 1976 was a bug nobody could see, and some mathematicians declined to call it a proof. Independent programs agreeing, then a formal proof whose trust rests on a small checking kernel rather than on the whole computation, have settled it for most. What the computer does not give is understanding: it confirms that four colours suffice without a short reason why, and none is known.

What has been built

The course began with questions of how many. The sum and product rules, bijections, binomial coefficients and inclusion and exclusion count without listing, and Probability rests on them, since a probability over equally likely outcomes is one count divided by another. Recurrences and generating functions describe a count through smaller ones, which is how Algorithms and Data Structures measures the running time of a program that calls itself. Divisibility, primes and congruences built RSA from Fermat's theorem, the starting point of Cryptography, and the same questions about primes pursued further are Number Theory. Graphs, trees and colourings proved what is true of networks, and Algorithms and Data Structures turns those proofs into methods for searching them and finding their shortest paths and spanning trees. Through all of it the method has been the same: find the right thing to count, set up an induction, and prove the answer right.