On this page
Have you ever tried to colour a map of India's 28 states and 8 Union Territories (Wikipedia)? If you use a new pencil for every state, you would need 36 different colours. But what if your only rule is that two neighbouring states cannot share the same colour? How many pencils do you actually need to complete the entire map without any borders blending together?
For over a century, some of the world's most brilliant mathematicians grappled with this deceptively simple question. The answer, no matter how complicated the map becomes, is exactly four.
What is the four colour theorem?
The four colour theorem guarantees that any map separated into connected regions can be coloured using no more than four colours, provided that no two adjacent regions share the same colour. It applies to any map drawn on a flat plane or the surface of a sphere, making it a fundamental rule of geometry and graph theory.
The problem was first proposed in 1852 by a student named Francis Guthrie. While he was colouring a map of the counties of England, he noticed that he never seemed to need more than four colours to separate the counties (Wikipedia). He shared this observation with his brother Frederick, who then brought it to the attention of his professor, the renowned mathematician Augustus De Morgan. Despite its simple premise, it remained an unsolved mathematical puzzle for over 120 years.
It was finally proven in 1976 by Kenneth Appel and Wolfgang Haken at the University of Illinois. Their proof was a landmark event: it was the first major mathematical theorem to be proved using a computer. Instead of a traditional handwritten mathematical proof, they wrote an algorithm that required the machine to analyse 1,834 unavoidable configurations over more than a thousand hours of computation (DOI: 10.1215/ijm/1256049011). This sparked a massive debate at the time about whether a proof that a human could not check by hand could be considered valid.
How to try map colouring with India?
You do not need a supercomputer to test this theorem yourself. Print an outline map of India and grab four differently coloured pencils.
Start at the edges: Pick a coastal state like Gujarat and colour it in with your first pencil.
Move inland: Move to its immediate neighbours, such as Rajasthan and Maharashtra, ensuring each gets a different colour. You are now using three pencils.
The trap of three colours: Try to limit yourself to just three colours for as long as possible. You will eventually hit a roadblock. For example, if you colour Maharashtra, Chhattisgarh and Karnataka with three different colours, you will find that Telangana (which touches all three of them) cannot be coloured without breaking the rule.
The fourth colour rescue: This is where your fourth pencil comes in. The moment you are trapped in a tight ring of states, the fourth colour will always resolve the conflict and let you continue.
Another excellent place to test this is the centre of the country. Look at Madhya Pradesh, which is landlocked and surrounded by five states: Uttar Pradesh, Rajasthan, Gujarat, Maharashtra, and Chhattisgarh. Because five is an odd number, if you try to alternate just two colours around the border of Madhya Pradesh, you will eventually have two states of the same colour touching. You will need a third colour for the surrounding ring, and a fourth colour for Madhya Pradesh itself.
If you enjoy visualising these geometric constraints and seeing how shapes interact, Euler's Formula for 3D Polyhedra: Finding V, E and F explores another fundamental mathematical rule that connects the vertices, edges, and faces of 3D objects.
Why do we never need five colours?
It seems entirely intuitive that a highly complex map, with a state completely surrounded by dozens of others, might eventually force you to pick up a fifth pencil. But topological rules prevent this from ever happening.
If you have a central state surrounded by a massive ring of other states, the outer states only ever need to alternate between two or three colours. A fourth colour can always be reserved for the central state. No matter how incredibly tangled the borders become on a flat surface, they can never form a configuration where five distinct regions all mutually touch each other. The geometry of a 2D plane simply does not have enough dimensions to allow five regions to all share borders simultaneously.
You can explore these graph theory principles directly in the Simulation Lab, which offers interactive simulations for the ideas that are easier to see than to read. While you experiment with different graphs, Fermi's AI tutor works out what you already know and teaches through the session. For more on mathematical arrangements and the logic of counting possibilities, you can also read about Derangements: how to count letters in the wrong envelopes.
