Extra material : Day 8

The extra stuff today consists of some brief remarks about planar graphs.

Definition : A graph is said to be planar if it can be drawn in the plane without any two edges crossing. If the graph is actually drawn in such a way then it is called plane.

There is a nice simple characterisation of planarity due to Kuratowski. First, we need a definition :

Definition : Let G, H be graphs. G is said to contain H as a minor if H can be obtained from G by a number of edge-contractions and deletions.

Theorem (Kuratowski) A graph is planar if an only if it does not contain either K_{5} or K_{3,3} as a minor.

Theorem (4-colour theorem) If G is a planar graph, then χ(G) ≤ 4.

This famous theorem was first proven in the mid ’70s. The main reason it is so famous is that it was the first long-standing open problem which was solved with substantial help from computers. The idea of the proof was to exhibit a finite collection of ‘minimal possible counterexamples’, that is, a finite collection of planar graphs such that, if each of these were 4-colourable, then it would follow that all planar graphs were. Such a list, consisting of about 10,000 graphs, was produced. And then the computers were called in to check that each of these graphs was indeed 4-colourable. In the ’90s a simplified version of the proof was obtained by Seymour, Robertson, ? and ??, which reduced the number of ‘test graphs’ to about 600.

Theorem (Euler) Let G be a plane graph. Let V denote the number of vertices in G, E the number of edges and R the number of regions into which G divides the plane, where we include the unbounded region outside G as one such. Then

V − E + R = 2.

Proof : I didn’t go through it, but the standard method is to use induction on the number of edges in G.

Remark : Let X be any compact, smooth surface in R^{3}. Let G be any graph drawn on this surface in such a way that no two edges cross and such that G divides the surface into simply-connected regions. If we compute V − E + R, then the result depends only on X, but not on G. This number is called the Euler characteristic of the surface X and denoted χ(X). See a textbook on Differential Geometry for more.