Chapter VII - The Case of the Hooded Man - Quick on the draw - Crime-Busting with a mathematical twist

Polytechnique > Quick on the Draw > Chapter VII - The Case of the Hooded Man

Chapter VII - The Case of the Hooded Man

To put a name to the hooded man in Chapter VII, Manori uses the concept of colouring the vertices in a graph. We already saw this in Chapter II. While Francis Guthrie was looking at the colouring of vertices in a planar graph, which can always be done using four colours, this concept can be extended to all graphs. Each vertex is assigned a colour in such a way that each edge has ends of two different colours. Many problems can be modelled using vertex colouring. In scheduling problems, for instance, we associate a vertex with each task, and we link two vertices with an edge when the two corresponding tasks are incompatible, in that they cannot take place simultaneously. Building a schedule, then, consists in colouring the vertices of the graph, each colour corresponding to a different time slot on the schedule. By requiring that the ends of an edge be of different colours, we avoid planning two incompatible tasks in the same slot. In the case of the hooded man, each vertex represents a prisoner, and an edge links two vertices if they did not work at the same place. Since the 17 prisoners were supposed to have been at one of the three hospitals in the city of Sion, three colours should have, in theory, been enough to colour in all the vertices of the graph. Manori noted that this was not the case, and he succeeded in demonstrating that it was only by removing Lambert from the graph (meaning vertex I) that he could obtain a colouring that didn't contradict the prisoners' statements.

Jensen and Toft's book provides more information about colouring problems, while Kubale's looks more specifically at extensions and generalizations of this concept, the aim being to use models that match reality as closely as possible.

Teaching notes - Vertex Colouring