Graph Colouring and Planarity
Colour vertices so that neighbours differ, bound the colours needed, and use Euler's formula to see what a graph drawn without crossings cannot contain.
What a learner can do afterwards
- Bound the chromatic number by the maximum degree and exhibit a graph meeting the bound
- Prove Euler's formula for connected planar graphs
- Use the edge bound from Euler's formula to show a specific graph is not planar
1 · Read
Coloring asks for the fewest colors with neighbours different. An even ring needs only two colors by alternation, while an odd ring or a clique needs more. Greedy order always manages with maximum degree plus one, and cliques show that bound is sharp. Timetables and maps turn straight into coloring problems.
For a connected drawing with no crossings, vertices minus edges plus faces equals two. That is Euler formula. Rearranged, faces equal 2 minus vertices plus edges. A drawing with 8 vertices and 12 edges therefore holds 6 faces. Counting edge face meetings then caps edges at 3 times vertices minus 6.
When a graph beats that edge cap, flat drawing is impossible. The complete graph on five vertices carries 10 edges against a cap of 9, so crossings are forced. Structure also trims color needs: a graph with no odd cycle splits into two sides, so two colors suffice, while a complete graph wants a fresh color per vertex.
To test flatness, count first and draw later. Work out vertices, edges, and the 3 times vertices minus 6 cap before sketching anything. Never confuse needing many colors with needing crossings: they are separate questions.
Color neighbours differently, count faces with Euler, and let the edge cap expose nonplanarity.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.