Traffic Control and Graph Theory

One of the compulsory modules for second year maths students is the second year essay, where we pick a topic in maths and write about it for the audience of other second-year maths students.

While researching for my essay, I came across Robbins’ Theorem, which states that:

A graph is orientable if and only if it is 2-edge-connected.

For a short sentence, that’s quite a bit of jargon, so I’ll break it down with an example.

We can think about a graph as road system – in this case, we’ll look at the main roads on central campus. A graph is made up of nodes (representing junctions, in this case) and edges (representing roads). For the purposes of our graph, we’ll trim out all of the little roads, and just leave the main ones.

Okay, so now we’ll look at the word "orientable". In terms of our road system, it is orientable if you can turn it into a one-way road system and be able to drive between any pair of junctions by following the one-way roads.

And then, there’s "2-edge-connected". In context of our road system, it means that we can make all of the roads two-way, then close a stretch of road between two adjacent junctions, and you’ll still be able to drive between any two junctions, by taking diversions around the closed road if necessary.

We’ve also got the structure of the sentence itself – "if and only if". This means that if a graph is orientable, then it is 2-edge-connected, and if a graph is 2-edge-connected, it is orientable.

I won’t go into proving the theorem here, but there’s a proof available here, for people who are interested. Note that this version uses the phrase "can be oriented to obtain a strongly-connected directed graph" to mean the same as our "orientable".

So, looking at our graph of campus, it’s pretty easy to check that removing any of the edges still leaves all of the nodes connected to the others in some way, so our graph is 2-edge-connected. Therefore, by Robbins’ Theorem, it must be orientable. We can find an example of a one-way road system that works:

You can test this out too – going from any node to any other node, just following the edges in the direction of the arrowhead.

This isn’t the only way of doing it, but, as is so often the case in maths, I’ll leave finding others as an exercise to the reader.