Christmas trees and the four-colour theorem

Mapmakers and tilers have found how elegant variation can be achieved with care

Christmas tree: When divided up by red, blue and gold kites and darts, no two adjacent regions are the same colour.

Christmas tree: When divided up by red, blue and gold kites and darts, no two adjacent regions are the same colour.

 

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.”

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

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
GO BACK
Error Image
The account details entered are not currently associated with an Irish Times subscription. Please subscribe to sign in to comment.
Comment Sign In

Forgot password?
The Irish Times Logo
Thank you
You should receive instructions for resetting your password. When you have reset your password, you can Sign In.
The Irish Times Logo
Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.
Screen Name Selection

Hello

Please choose a screen name. This name will appear beside any comments you post. Your screen name should follow the standards set out in our community standards.

The Irish Times Logo
Commenting on The Irish Times has changed. To comment you must now be an Irish Times subscriber.
SUBSCRIBE
Forgot Password
Please enter your email address so we can send you a link to reset your password.

Sign In

Your Comments
We reserve the right to remove any content at any time from this Community, including without limitation if it violates the Community Standards. We ask that you report content that you in good faith believe violates the above rules by clicking the Flag link next to the offending comment or by filling out this form. New comments are only accepted for 3 days from the date of publication.