Only two colours are needed for the upper four faces of the octahedron. If, for example, blue and red are used then these four faces may be painted alternately red and blue. Consider now the lower four faces: every face adjacent to an upper blue face may be painted red and every face adjacent to an upper red face may be painted blue. So only two colours are required for the whole
This problem is taken from the UKMT Mathematical Challenges.