Graph Colouring Challenge Generator
Give every node a colour so that no edge has the same colour at both ends. It is the abstract form of scheduling exams without clashes, assigning radio frequencies, or colouring a map. The greedy answer depends entirely on the order nodes are visited, so a good colouring is easy and the fewest possible is hard — and where the graph is small enough this page searches for one fewer colour and reports whether it exists.
What this generator does
Colours the graph greedily in largest-degree-first order, reports how many colours that took, and states the bound every graph obeys: no graph ever needs more than one colour beyond its largest degree. At ten nodes or fewer it also searches exhaustively for a colouring with one colour less.
How to use this tool
- Choose the graph size and density.
- Colour every node so no edge has matching ends.
- Compare against the colouring shown and its colour count.
- Check whether the minimum was proved for that graph.
Understanding the controls
- How many nodes
- Between 4 and 12. The minimum-colour proof runs at ten and below, where the exhaustive search stays instant.
- Extra edge density (%)
- Denser graphs need more colours. A graph with no edges needs one; a complete graph needs as many colours as it has nodes.
- Seed
- Reproduces the same graph, so a colouring problem can be set and marked.
Common use cases
- Practice at proper colouring with an answer to check against
- Showing why greedy colouring depends on the visiting order
- Introducing the chromatic number as a searched-for quantity, not a formula
- Exam-timetabling and frequency-assignment examples in abstract form
- Producing the same graph twice from a seed
How this generator works
Greedy colouring gives each node the lowest colour none of its neighbours has taken. The check walks every edge and requires different colours at its ends, confirms the count matches the colouring, and where the minimum is claimed re-runs the exhaustive search for one fewer colour to make sure none exists.
Randomness and fairness
The graph is random; the colouring and the bound are computed, and the minimum claim is proved by search rather than asserted. Seeded graphs reproduce exactly and are therefore explicitly not cryptographically secure. Unseeded, the browser's cryptographically secure generator is used.
For how randomness is produced across the whole site, see how Generate Random works.
Limitations and good to know
- The colouring shown is greedy, so above ten nodes it may use more colours than necessary and the page says so.
- Only vertex colouring — edge colouring and list colouring are different problems.
- Colours are shown as swatches and numbers rather than applied to a drawing of the graph.
- Graphs are undirected and simple, with no repeated edges or self-loops.
- Nothing is stored between visits; seed a graph you want again.
Privacy and your data
The graph and the colouring are computed in your browser. No graph, colouring or seed is transmitted or stored.
Related generators
- Bipartite Graph GeneratorGraphs split into two sides with every edge crossing, or a graph that cannot be — with the odd cycle that proves it.
- Random Graph GeneratorRandom graphs at a density you choose, drawn and exported as an edge list or DOT, with connectivity measured rather than assumed.
- Minimum Spanning Tree GeneratorWeighted graphs with the cheapest spanning tree found by Kruskal and, at small sizes, confirmed against every other spanning tree.
- Sudoku GeneratorPrint a sudoku with exactly one solution — 4x4, 6x6 or full 9x9, four difficulties, with the answer key and a seed to reprint it.