A colouring proof is a sort of invariant proof which can mainly be used to prove that something isn’t possible. The essence of invariant proofs is to strip the problem of any unnecessary details and only keep the information that best describes why something isn’t possible, making it very easy to follow invariant proofs.

They do this by finding something that is invariable, constant, doesn’t change over the course of the problem, making everything that would require this constant to change, be impossible. colouring proofs are invariant proofs that have invariants that show up when you colour in the correct pattern.Making them a perfect methodto tackle tiling problems, which can easily hold patterns. Here, next we have a simple example that demonstrates the power of colouring. A commonly used type of colouring is chessboard colouring. An easy example:

‍

Problem: Is it possible to make a walk on an 8×8 board with squares such that you walk on each squareexactly once such that your start and end positions are in opposite corners? You are only allowed to walk to an adjacent square.

Solution:

By colouring the board in a chessboard pattern we notice that while standing on a white square we may only move to a black one and vice versa. The starting corner can be either black or white, it does not matter. There are 63 squares left to walk on, which means 63 moves remain. If we start in a white corner, our first move will be to a black square. Our second move is to a white square and our third is to a black square. We can see that every odd move is to a black square and every even move is to a white square.This fact is our invariant. No matter how we move, every odd move will still be to a black square and every even move will still be to a white square. We make 63 moves, so our last move is to a black square. However, opposite corners have the same colour, namely white, so we cannot end in the opposite corner of the one we started in.

‍

Some useful colourings: