Facebook and Twitter were born in 18th century Europe
In the early 1700s, the good people of Königsberg in Prussia had a problem on their minds. There were seven bridges that crossed the river in that town, and the big question was: could a route be found that allowed someone to cross all seven bridges without crossing any one bridge more than once?
Why exactly this was a concern is lost to history. Perhaps there were tolls on the bridges and people were trying to find the cheapest way about town? Or perhaps they were scared or bored of bridges? In any case, the point is that Facebook and Twitter owe a lot to the man that solved this problem.
That man was the Swiss-born mathematician Leonhard Euler. Euler seized the problem of the Königsberg bridges with the relish that only a true mathematician could have for a problem like this. And like a true mathematician always does, he reduced it to its simplest form. This problem was not about bridges — it was about something much simpler. What it reduced to was this: can you draw this graph with a pencil without crossing the same line twice and without taking your pencil off the paper:
The answer is no — give it a try! And with that simple insight was born a branch of mathematics that is central to every like, every follow, every friend request that we send on our smartphones or computers today: graph theory!
What are graphs?
Most people understand the term ‘graph’ very broadly, to represent most mathematical pictorial depictions. However, as you’d expect, in mathematics there is a very clear definition of what a graph is which allows us to set up helpful rules and calculations around them to make them useful to the problems we are trying to solve.
In its most abstract form, a graph is two sets. The first set is called the vertex set. You can think of this as a set of different objects: for example it could be people, or it could even be sewer junctions (more on this in a later article). Sewers can smell a bit, so lets stick…