Graph theory

Colouring a graph is simple to state and surprisingly hard to optimise.

This prototype introduces graph colouring through greedy algorithms. Learners can step through choices, see which colours are forbidden, and compare how ordering changes the result.

The aim is to connect a visual puzzle with deeper ideas in discrete maths, algorithms, timetabling and optimisation.

Graph colouring lab

Colour adjacent vertices differently

A graph colouring assigns colours to vertices so that no two connected vertices share a colour. Step through a greedy algorithm and compare how the chosen order affects the result.

Vertices

Edges

Colours used

Known minimum

Reveal by finishing

Controls

Graph

Algorithm order

Step 1 of 6

Start with every vertex uncoloured. The greedy algorithm colours one vertex at a time.

Colouring order: V1, V2, V3, V4, V5

Forbidden colours now: none

What this shows

An odd cycle cannot be coloured with only two colours. This is the classic first surprise.

Greedy colouring is fast and intuitive, but it does not always use the fewest possible colours.

This is a doorway into optimisation, timetabling, register allocation and hard computational problems.

Guided tasks

Predict the colour before pressing Next step. Which neighbouring colours are forbidden?

Compare the two ordering strategies. Do they always use the same number of colours?

Explain why the odd cycle needs three colours but the bipartite graph only needs two.

Joy in the process

The point is not just to finish. It is to notice, test and return.

These tools are invitations to explore. A good mistake, a surprising pattern or a question you cannot yet answer is part of the work, not a failure of it.

The challenge is deliberate: the site should support thinking, not remove the need for it.

Before changing a setting, pause and predict what you think will happen.

Change one thing at a time. What stayed the same, and what changed?

Try to create a surprising case, a broken case, or a beautiful pattern.

Ask what this connects to outside the page: maps, movement, nature, systems or decisions.

Reset, then try again with a new question in mind.

Future extensions

This can become a deeper graph algorithms playground.

Add editable graphs so learners can create their own colouring problems.

Add greedy failure cases where the algorithm uses too many colours.

Add Welsh-Powell, backtracking and optimal colouring comparisons.

Add timetable and map-colouring contexts for classroom discussion.