- Mathematics
- Class 11
- Project 24
24No Two Exams at Once: Timetables by Graph Colouring
Making an exam or club timetable where no student has two things at the same time is a famous mathematical puzzle. Teams turn the problem into a graph, with a point for each subject and a line between any two subjects that share a student, and then colour the points so that joined points have different colours. Each colour is a time slot. They find the fewest slots needed and design a fair timetable for a real school event.
- Class and age
- Class 11 · 16–17
- Activity type
- Group
- Time needed
- 2 sessions of 60 minutes
- Difficulty
- Challenging
- Estimated budget
- ৳0–৳20
Mathematical concepts
- Conflict graphs
- Graph colouring and the chromatic number
- The greedy colouring algorithm
- Lower bounds from triangles and cliques
- Constraints and fairness in scheduling
Learning objectives
- Model a scheduling problem as a graph.
- Colour a graph using a clear algorithm.
- Prove a lower bound on the number of slots.
- Design and justify a timetable for a real event.
Real-life connection
Universities schedule exams, airlines assign gates, radio stations choose frequencies so they do not interfere, and phone networks share channels, all using graph colouring ideas.
Materials required
- Chart paper and coloured pens or stickers
- A list of which students take which subjects or clubs (anonymous, from the teacher or a class survey)
- Optional: a spreadsheet
Step-by-step instructions
- Warm up: subjects P, Q, R, S, T. Pairs sharing students: P-Q, P-R, Q-R, R-S, S-T. Draw the conflict graph.
- Colour it with the fewest colours you can so that joined points differ. How many colours did you need?
- Find a triangle (three points all joined). Explain why a triangle forces at least 3 colours.
- Learn the greedy algorithm: list the points (largest number of lines first), give each the first colour not used by its coloured neighbours.
- Collect real, anonymous data: which subjects, clubs or competition events each student is in.
- Build the real conflict graph and colour it with the greedy algorithm. Try a different order. Does the number of colours change?
- Add real constraints, for example no student should have more than two exams in one day, or a hall is free only in the morning.
- Present a final timetable, the graph, and a short proof of why it cannot be done with fewer slots (if you can find one).
Mathematical explanation
In the warm-up, P, Q and R form a triangle, so they need three different slots, and 3 is a lower bound. Three colours are enough: P = slot 1, Q = slot 2, R = slot 3, S = slot 1 (S is joined only to R and T), T = slot 2. So the minimum, called the chromatic number, is exactly 3. The greedy algorithm is fast and always gives a valid timetable, but it does not always give the minimum; a different order can save a slot. For large graphs, finding the true minimum is one of the hardest known problems in computer science, so real schedulers combine clever algorithms with good lower bounds such as the largest group of mutually clashing subjects.
Expected project output
The coloured warm-up graph, the real conflict graph, a final timetable with constraints, and a short written argument about the minimum number of slots.
Skills developed
- Graph modelling
- Algorithmic thinking
- Proof by lower bound
- Practical planning with constraints
Assessment criteria
- The warm-up is coloured with 3 colours and the triangle argument is explained.
- The real graph is built correctly from the data.
- The greedy algorithm is applied correctly.
- The timetable satisfies all the stated constraints.
Extension challenge
Look up the Four Colour Theorem for maps. Colour a map of the divisions of Bangladesh so that neighbouring divisions have different colours. How few colours do you need?
Safety and inclusion
Use student numbers or codes instead of names when collecting subject or club lists, and keep the list inside the class.