BTT Mathematics / Primary Mathematics Learning Hub / Graph Coloring
A proper graph coloring assigns colors to vertices so that adjacent vertices receive different colors. The chromatic number χ(G) is the smallest number of colors that can properly color the graph.
The colors themselves are only labels. Red, blue and green could just as well be 1,2,3. The mathematics lies in the adjacency restrictions and in proving that fewer colors cannot work.
For a triangle, every vertex touches the other two, so three colors are necessary and sufficient: χ=3. For a square cycle, alternating two colors works, so χ=2.
This guide is Primary Mathematics enrichment. It connects Route Networks, Logic, Deduction and Truth Conditions, Optimisation and Multiple Constraints.
Formal graph theory is optional enrichment. Use the MOE Primary curriculum page and the learner’s school programme for required scope.
Proper coloring · Chromatic number · Paths and cycles · Complete and bipartite graphs · Map coloring · Proving minimum colors · 24 questions · Worked answers
1. Adjacency, not physical closeness, controls the coloring
Two vertices are adjacent when an edge joins them. Vertices drawn close together but not connected may use the same color.
Worked example A: One edge
A graph with two vertices joined by one edge needs 2 colors.
Worked example B: Three isolated vertices
No edges means no adjacency conflicts, so all three vertices may use one color. The chromatic number is 1.
Worked example C: A path of four vertices
For A—B—C—D, color A and C red, B and D blue. Two colors work.
Worked example D: Improper coloring
If adjacent vertices B and C are both blue, the coloring fails even if every other edge is proper. Every edge must join differently colored endpoints.
2. Chromatic number is a minimum, so it needs two arguments
To prove χ(G)=k, show:
1. Upper bound: a proper coloring with k colors exists.
2. Lower bound: fewer than k colors are impossible.
Worked example E: Triangle
Three vertices are pairwise adjacent. They must all have different colors, giving a lower bound of3. A three-coloring exists, so χ=3.
Worked example F: Square
An edge proves at least2 colors are needed. Alternating colors around the square gives a two-coloring. Therefore χ=2.
Worked example G: Complete graph K4
Every pair of four vertices is adjacent. All four must have different colors, so χ(K4)=4.
Worked example H: A star
One center is joined to several leaves, but leaves are not joined to one another. Color the center red and all leaves blue. If at least one edge exists, χ=2.
3. Paths and cycles reveal a parity pattern
Every path containing at least one edge is two-colorable by alternating colors from one end to the other.
Worked example I: Five-vertex path
A—B—C—D—E can be colored red, blue, red, blue, red. Hence χ=2.
Even cycles
An even cycle returns to the starting point after an even number of alternations, so two colors remain consistent.
Worked example J: Six-cycle
Alternating red and blue around C6 works. χ(C6)=2.
Odd cycles
An odd cycle returns to the start after an odd number of alternations. The last vertex then demands the same color as the start even though the two are adjacent, so two colors fail.
Worked example K: Pentagon cycle
C5 cannot use two colors, but three colors work. Therefore χ(C5)=3.
Worked example L: Seven-cycle
The same parity argument gives χ(C7)=3.
4. Complete and bipartite graphs sit at opposite extremes
In a complete graph Kn, every pair of distinct vertices is adjacent. Therefore each vertex needs its own color and χ(Kn)=n.
Worked example M: K5
Five pairwise adjacent vertices require 5 colors.
A bipartite graph divides its vertices into two groups so that every edge goes between the groups and no edge stays within one group.
Worked example N: Complete bipartite K2,3
Color the two vertices in the first part red and all three in the second part blue. Since the graph has edges, χ=2.
Worked example O: Trees
Every tree with at least one edge is bipartite, so it is two-colorable. Start at any vertex and color by even/odd distance from it.
Worked example P: Clique lower bound
If a graph contains a triangle somewhere inside it, the whole graph needs at least3 colors because those three mutually adjacent vertices already require three.
5. Map coloring becomes graph coloring through region adjacency
Turn each region into a vertex. Join two vertices when the corresponding regions share a boundary segment. Merely touching at one point does not count as adjacency under the usual map-coloring convention used here.
Worked example Q: Chain of regions
If A touches B and B touches C, but A does not touch C, two colors suffice: A red, B blue, C red.
Worked example R: Three pairwise adjacent regions
If A, B and C each share boundary segments with both others, the dual graph is a triangle and needs 3 colors.
Worked example S: Four-region ring
Regions arranged in a cycle A-B-C-D-A can use two alternating colors if opposite regions are not adjacent.
Four-color context
A famous theorem says every planar map can be properly colored using at most four colors under the standard boundary-adjacency convention. This guide does not prove that theorem; its exercises use small maps where the minimum can be checked directly.
6. Lower bounds and constructions work together
A coloring with k colors proves χ≤k. It does not prove χ=k until fewer colors are ruled out.
Worked example T: Triangle plus a leaf
A triangle needs at least3 colors. Attach one extra leaf to one triangle vertex. The leaf can reuse either of the other triangle colors, so three colors still suffice. Hence χ=3.
Worked example U: Square with one diagonal
The diagonal creates a triangle among three of the square’s vertices, so at least3 colors are needed. A three-coloring exists, so χ=3.
Worked example V: Square with both diagonals
All four vertices become pairwise adjacent: the graph is K4. Therefore χ=4.
Worked example W: Greedy coloring is not automatically optimal
A procedure that chooses the first available color may use more colors than necessary if vertices are processed in an unfortunate order. A valid coloring is an upper bound; optimality requires a separate minimum argument.
7. Practice: 24 original questions
Questions 1–8: Proper coloring and chromatic number
1. What is the chromatic number of a graph consisting of one isolated vertex?
2. What is the chromatic number of one edge?
3. What is χ for a path with five vertices?
4. What is χ for a triangle?
5. What is χ for a square cycle?
6. What is χ(K4)?
7. What is χ(K5)?
8. Why does exhibiting a three-coloring not by itself prove χ=3?
Questions 9–16: Parity, bipartite structure and lower bounds
9. What is χ(C6)?
10. What is χ(C7)?
11. What is χ(C8)?
12. What is χ(C9)?
13. What is χ of a non-trivial star graph?
14. What is χ(K2,3)?
15. A graph contains a triangle. What lower bound does that give for χ?
16. Why is every tree with at least one edge two-colorable?
Questions 17–24: Maps and constructions
17. Three regions form a chain A-B-C with A not adjacent to C. How many colors are sufficient?
18. Three regions are pairwise adjacent. What minimum is required?
19. Four regions form only the cycle A-B-C-D-A. How many colors suffice?
20. Two regions touch only at one point. Are they adjacent under this guide’s map convention?
21. A square graph receives one diagonal. What is its chromatic number?
22. The same square receives both diagonals. What is its chromatic number?
23. A triangle has one leaf attached to one vertex. What is its chromatic number?
24. State the two parts needed to prove an exact chromatic number k.
8. Worked answers
Answers 1–8
1. 1.
2. 2.
3. 2. Alternate colors along the path.
4. 3.
5. 2.
6. 4.
7. 5.
8. It proves only χ≤3. You must also show that one or two colors are impossible as appropriate.
Answers 9–16
9. 2.
10. 3.
11. 2.
12. 3.
13. 2.
14. 2.
15. χ≥3.
16. Choose a root and color vertices by even or odd distance from it. Every tree edge joins consecutive distance levels.
Answers 17–24
17. 2 colors.
18. 3 colors.
19. 2 colors.
20. No. Point-only contact does not count as adjacency here.
21. 3. The diagonal creates a triangle.
22. 4. The graph becomes K4.
23. 3.
24. A k-color construction giving χ≤k, and a lower-bound argument showing χ≥k.
9. Teaching and transfer
If a learner colors by visual distance, replace the picture with an adjacency list. Only edges matter.
When too many colors are used
A proper coloring can still be inefficient. Ask which non-adjacent vertices could safely share a color.
When too few colors are claimed
Search for a forced structure such as an odd cycle or clique. A small subgraph can provide a lower bound for the entire graph.
When map corners cause confusion
State the convention before coloring: shared boundary segment means adjacent; a single touching point does not.
When parity feels unrelated
Walk around a cycle alternating two colors. Even cycles return with the correct opposite color; odd cycles return with a conflict.
Connect to constraint satisfaction
Graph coloring is another finite constraint problem: each vertex has a candidate color set, and every edge removes same-color combinations. This connects naturally to Latin Squares, Sudoku Structure and Constraint Propagation.
Continue through this enrichment collection
For recursive states, use Tower of Hanoi, Recursion and State Transitions. For nearest-region partitions, use Voronoi Diagrams, Nearest Regions and Geometric Partitioning. For repeated local update rules, use Cellular Automata, Local Rules and Emergent Patterns.
Return to the BTT Primary Mathematics Learning Hub.
Original enrichment guide with 24 original practice questions and separate worked answers. Map adjacency conventions are stated explicitly; advanced planar-map theorems are context only.