Christmas trees and the four-colour theorem

When decorating our Christmas trees, we aim to achieve an aesthetic balance. Let’s suppose that there is a plenitude of baubles, but that their colour range is limited. We could cover the tree with bright shiny balls, but to have two baubles of the same colour touching might be considered garish. How many colours are required to avoid such a catastrophe?

The answer rests on the four colour theorem. This assures us that, for any map, no matter how complicated, not more than four different colours are required to ensure that no two neighbouring regions have the same colour. A county map of Ireland makes it clear that three colours are insufficient.

Co Laois is bordered by five counties. Colouring Laois blue we need three more colours to guarantee that no two of the surrounding counties sharing a boundary are the same colour; for example, if Offaly and Carlow are green, and Kildare and Kilkenny yellow, then Tipperary, which borders Laois, Offaly and Kilkenny, must be red.

Four-colour conjecture

The four-colour problem was first considered in 1852 by Francis Guthrie, who noticed that he needed just four colours for a map of the counties of England. The mathematician Augustus de Morgan, hearing of the conjecture, wrote to his friend the distinguished Irish mathematical physicist William Rowan Hamilton, hoping to interest him in the problem, but Hamilton's reply was terse: "I am not likely to attempt your 'quaternion' of colours very soon."

The race to understand the impact of Covid-19 on the heart

---

Student’s joint injury rehabilitation monitoring system wins SciFest 2020

---

European Space Agency satellite to provide key indications of rise in sea level due to climate warming

---

Ireland’s mapping grid in harmony with GPS

---

Several alleged proofs of the four-colour conjecture appeared over the ensuing decades, but all were found to be flawed. The conjecture was eventually proved in 1976 by Kenneth Appel and Wolfgang Haken of the University of Illinois. Their proof was controversial, as it depended essentially on output from a computer program. Drastically simplified proofs have since appeared, but the search continues for a proof that does not require the use of a computer.

Things are simpler for the Christmas tree problem than for a general map. If we have baubles of four colours, we are assured by the theorem that there is a way to arrange them so that no two isochromic baubles touch each other. However, although the solution must exist, it may be difficult to find. If all the baubles are the same size, they can be arranged in a regular pattern like the squares of a chess-board, and two colours suffice. But this is unlikely to appeal. A more interesting pattern is the honeycomb, made up of hexagons, which requires just three colours.

Kites and darts

Many other delightful possibilities arise with three colours. In the 1970s, mathematician and physicist Roger Penrose investigated aperiodic schemes for tiling the plane. For an aperiodic tiling, a shift by any distance without rotation will never produce the same pattern. Earlier schemes used many different tile shapes, but Penrose found he could tile the plane aperiodically using just two shapes, called kites and darts.

The illustration shows a Christmas tree divided up by red, blue and gold kites and darts, arranged so that no two adjacent regions are the same colour. Replacing each colour patch by a glittering globe, we should achieve a stunning decoration of the tree.

Peter Lynch is emeritus professor at the school of mathematics and statistics at University College Dublin. He blogs at thatsmaths.com