Skip to main content
Home
plus.maths.org

Secondary menu

  • My list
  • About Plus
  • Sponsors
  • Subscribe
  • Contact Us
  • Log in
  • Main navigation

  • Home
  • Articles
  • Collections
  • Podcasts
  • Maths in a minute
  • Puzzles
  • Videos
  • Topics and tags
  • For

    • cat icon
      Curiosity
    • newspaper icon
      Media
    • graduation icon
      Education
    • briefcase icon
      Policy

      Popular topics and tags

      Shapes

      • Geometry
      • Vectors and matrices
      • Topology
      • Networks and graph theory
      • Fractals

      Numbers

      • Number theory
      • Arithmetic
      • Prime numbers
      • Fermat's last theorem
      • Cryptography

      Computing and information

      • Quantum computing
      • Complexity
      • Information theory
      • Artificial intelligence and machine learning
      • Algorithm

      Data and probability

      • Statistics
      • Probability and uncertainty
      • Randomness

      Abstract structures

      • Symmetry
      • Algebra and group theory
      • Vectors and matrices

      Physics

      • Fluid dynamics
      • Quantum physics
      • General relativity, gravity and black holes
      • Entropy and thermodynamics
      • String theory and quantum gravity

      Arts, humanities and sport

      • History and philosophy of mathematics
      • Art and Music
      • Language
      • Sport

      Logic, proof and strategy

      • Logic
      • Proof
      • Game theory

      Calculus and analysis

      • Differential equations
      • Calculus

      Towards applications

      • Mathematical modelling
      • Dynamical systems and Chaos

      Applications

      • Medicine and health
      • Epidemiology
      • Biology
      • Economics and finance
      • Engineering and architecture
      • Weather forecasting
      • Climate change

      Understanding of mathematics

      • Public understanding of mathematics
      • Education

      Get your maths quickly

      • Maths in a minute

      Main menu

    • Home
    • Articles
    • Collections
    • Podcasts
    • Maths in a minute
    • Puzzles
    • Videos
    • Topics and tags
    • Audiences

      • cat icon
        Curiosity
      • newspaper icon
        Media
      • graduation icon
        Education
      • briefcase icon
        Policy

      Secondary menu

    • My list
    • About Plus
    • Sponsors
    • Subscribe
    • Contact Us
    • Log in
    • Do five suffice solution

      1 December, 2008
      December 2008

      Do five suffice?

      Until yesterday Queen Griselda's empire had an annoying hole right in the middle of it, due to a kingdom of small, but remarkably resistant, dwarves. The hole stuck out like a sore thumb in the magnificent map painted on the wall above her throne. Yesterday, though, the Queen's army finally forced the dwarves into submission.

      Triumphant though she is, she now has a new problem. The map above her throne is coloured with the five colours of her coat of arms: silver, gold, purple, blue and red. The kingdom of dwarves is surrounded by exactly five countries of her existing empire, and these five countries each use one of the five favourite colours. Obviously, she doesn't want neighbouring countries to have the same colour, and so far she has been able to avoid this. Will she now have to find a sixth colour for the new country, thus breaking the pleasing colour correspondence between her map and her coat of arms?

      Wurzel the Wizard reassures her: it's possible, he says, to recolour the countries so that five colours suffice for the new map. Can you prove that he is right?

      The solution

      The problem becomes easier when you replace each country by a coloured dot, with a line connecting two dots if the corresponding countries are neighbours. The resulting object is called a graph, and we note that no two lines in the graph cross. Now look at dots representing the five countries that are neighbours of the new one, and label them by the numbers 1, 2, 3, 4, and 5, in cyclical order.

      Now dot 1 and dot 3 are not adjacent, so let's see what could possibly stop us from recolouring dot 3 (which is, say, red) with the colour of dot 1 (blue). If we recolour dot 3 in blue, then we have to recolour all other blue dots that are connected to dot 3, for otherwise we break the rule that adjacent dots must have different colours. So let's recolour these other blue dots in red. This in turn will force us to recolour a third generation of dots, namely those that are red and connected to those dots we've just recoloured in red.

      You can see that this recolouring will effect all dots that are either blue or red and that are connected to dot 3 by some path in our graph. If dot 1 is not one of these, then we are done: we simply swap the colours of those dots that are blue or red and connected to dot 3 by some path.

      If dot 1 is connected to dot 3 by some path that passes through blue and red dots only, then we turn our attention to dots 2 and 4. By the same argument, the only thing that could stop us from repainting dot 4 (which is gold) in the colour of dot 2 (purple) would be a path from dot 2 to dot 4 that passes though purple and gold dots only. But because of the nature of our graph, such a path would have to cross the path from dot 1 to dot 3. Since no lines in our graph are allowed to cross, such a path cannot possibly exist. We can therefore paint dot 4 in purple, make the corresponding changes to the gold and purple dots that are connected to dot 4, and use the colour gold for the new country in the middle.

      If you have solved this puzzle, then you have almost proved the five colour theorem. The theorem states that any two-dimensional map can be coloured using at most five colours so that no two neighbouring countries have the same colour. To prove this, you start by assuming that there are maps that use six colours and choose one with the smallest number of countries. Now this map clearly contains a country with at least five neighbours that together use up five colours (otherwise you wouldn't need six colours). It's possible to show that in fact that country has exactly five neighbours. If you remove that country, you get a smaller map which, by our assumption, can be coloured by five colours. Now you're in the situation of our puzzle: using the arguments from above, you can show that the map can be recoloured using just five colours. This is a contradiction, because we assumed that the map needed six colours, so our original assumption must be false. QED.

      This does of course beg the question of whether we can reduce the necessary number of colours to four. The answer is yes, we can, but the proof is nowhere near as easy as the one for five colours. In fact, some would argue that no one has as yet found a proof, as the existing one relies on computers checking a vast number of possible configurations. No human could ever verify the computer calculations, so there is doubt as to whether the proof is valid. To find out more about the four colour theorem, read The philosophy of proof and Plus 100 — the best maths of the last century.



      Back to main puzzle page
      • Log in or register to post comments
      University of Cambridge logo

      Plus Magazine is part of the family of activities in the Millennium Mathematics Project.
      Copyright © 1997 - 2025. University of Cambridge. All rights reserved.

      Terms