Chapter II - The Villas of the Bellevue - Quick on the draw - Crime-Busting with a mathematical twist

Polytechnique > Quick on the Draw > Chapter II - The Villas of the Bellevue

Chapter II - The Villas of the Bellevue

The second chapter is devoted to "planar" graphs. These are graphs that can be drawn on a flat surface without any of the edges crossing over one another. When we draw a graph with edges that do cross, that doesn't mean it isn't planar. It's possible that by moving the vertices, we may succeed in avoiding all crossovers. A good example is provided in the last chapter, when Manori tries to solve the second Sudoku grid. The first graph proposed by the Sudoku apprentice includes several crossovers. For example, the edge linking vertex A to vertex 3 crosses four other vertices-those linking D to 1, D to 2, E to 1 and E to 2. Manori then draws another representation of that same graph, but avoiding all crossovers this time. The graph that Lei draws is therefore planar.

Planar graphs were popularized by the Scotsman Francis Guthrie who, in 1852, wondered if it were possible to colour all maps using only four colours, without two neighbouring countries ever being of the same colour. By representing each country by a vertex and linking two vertices with an edge if, and only if, the two countries represented by these vertices have a common border, we get a planar graph. So Francis Guthrie essentially wanted to know whether it were possible to colour the vertices of a planar graph using only four colours, with the sole constraint being that the ends of each edge must be of different colours (which is equivalent to asking that countries with a common border be of different colours). It was only in 1976 that Kenneth Appel and Wolfgang Haken succeeded in demonstrating that four colours are always sufficient (see Appel, 1989). This proof required the intensive use of computers, and it is impossible to verify by hand whether all the cases processed by computer are free of error. The mathematics community is currently split into two camps-those who definitively accept the demonstration and those who think nothing has been proven yet. Efforts have been made to simplify the demonstration. A shorter version appeared in Robertson et al.

Planar graphs were the subject of many studies long before Francis Guthrie asked his colouring question. For example, as mentioned in Chapter II, the famous Swiss mathematician Leonhard Euler demonstrated in 1736 that there is a link between the number of vertices, the number of edges and the number of faces in a planar graph. Readers interested in planar graphs can learn much more by reading, for example, Nishizeki and Chiba's book.

Teaching notes - Planar Graphs