Fun Graph Theory (bonus content)
I was originally going to include the following anecdote in my blogpost on graph theory, but decided against it as it was unnecessarily confusing and didn't actually teach any graph theory. However, that shouldn't detract from its original aim. The main blogpost can be found here: https://allovertwoa.blogspot.com/2024/06/fun-graph-theory.html
The childhood example
When I was younger, I had an ambitious plan to create a massive map of all the main bus routes in London as if in the style of the Tube map. If I had about seven hundred colours, this would have been easy to achieve - many modern computers can show millions of colours through merging red, green and blue. However, I only had about forty, and to this day it's still not been finished. Yet if I knew more about graph theory, I'd have known just how impractical this scheme actually was.
Here are the conditions to complete the bus map:
Forty colours are available
Each route (from seven hundred total) is assigned one colour
Colours can be reused, so long as they do not overlap with other routes of the same colour
Let's use Croydon as an example; say I made the 109 blue. None of the routes in Croydon can be blue - instead, I'll assign the other thirty-four routes thirty-four of the other colours. From here, there's a massive ripple effect - none of the bus routes in Brixton can be blue, so the seventeen other routes must be assigned different colours. From here, blue can finally be used, but the other colours still need to be used, and you're bound to get an overlap somewhere.
This reminds me in a way of the four colour map theorem, which states that the minimum number of colours needed to fill in a map such that no colours meet is four. Proof by computer was required to finally solve the problem in the 1970s; loads of proofs had been made, and all soon fell apart. In many ways, the theorem solves a simpler problem than my bus map problem because there are fewer links to be made.
*Could there ever be a solution to the "bus map problem"?*
I reckon there could be, the only issue being that there are so many permutations and nodes that to get a solution would require me to go through all the solutions by brute force. I believe such a map is impossible when using London's night buses, however, which at first is surprising because there are far fewer routes - yet almost all of them congregate around Trafalgar Square, Aldwych and Oxford Circus, so there are loads of overlaps almost immediately.