Recently, a friend asked for help with a tricky problem: they were staging a play, and the script had a large number of characters. They didn鈥檛 want to hire an actor for each role, and while they could double up, they would run into problems if the same actor were playing two characters in a scene.
Luckily, I was the right person to come to for help. There鈥檚 a piece of maths that鈥檚 effective at solving many such problems, from casting a play to timetable scheduling 鈥� and even colouring in.
Graphs 鈥� networks of points joined by lines are extremely effective for modelling sets of objects and the relationships between them, with obvious uses in describing structures like computer networks or roads between cities. Mathematicians are often particularly interested in the properties of graphs because they tell us something more about the underlying structure.
Advertisement
One such property is graph colouring. This involves assigning a colour to each point, so that any two points joined with a line are assigned different colours. Finding the minimum number of colours needed to do this can tell us something useful about the graph鈥檚 structure. For example, a graph with a triangle of points all joined to a fourth point in the centre will need at least four colours to fill it in.
One application is in problems involving actual colouring: given a picture split into connected regions, is there a way to fill it in using only a limited set of colours, so adjacent regions are different hues? The proof of the four colour theorem confirmed that for diagrams drawn on paper, four colours at most will ever be needed. These correspond to graphs that can be drawn on a page without any lines crossing.
Even if a graph can鈥檛 be drawn without crossings, we can still find the minimum number of colours needed to fill it in, and use this to solve problems.
One of my favourite uses of graph colouring is in scheduling problems: imagine a set of classes, with a shared set of students. We can draw a graph, indicating each class by a point, and join two points if those classes have any students taking both (so they can鈥檛 happen at the same time).
Then, we find a way to colour the graph using the fewest possible colours. The minimum number of colours will tell us how many timetable slots we will need: each colour represents a set of classes with no overlap in students, so they can all happen simultaneously.
This may tell you how I solved my friend鈥檚 problem: I suggested they draw a graph, representing each character with a point, and join two characters with a line if they appeared in any scenes together. Colouring this graph minimally then told them exactly how many actors they would need to stage the play. Another victory for maths 鈥� on with the show!
Katie Steckles is a mathematician, lecturer, YouTuber and author based聽in聽Manchester, UK. She聽is also聽adviser for New聽Scientist鈥檚 puzzle column,聽BrainTwister. Follow聽her聽@stecks
For other projects visit newscientist.com/maker
