Origin of Graph Theory

Intrigued by our recent experiments within AI Labs using #neo4j (graph database), I have been trying to trace the origin of Graph Theory and how it evolved. Here goes the story-

In the 18th century, Königsberg was a historic medieval city in Russia that is now named Kaliningrad. This medieval city lay on both sides of the Pregel River. At the center were two large islands. The two islands were connected to each other and to other river banks by seven bridges.

Carl Gottlieb Ehler, a mathematician who later became the mayor of a nearby town, grew obsessed with these islands and bridges. He kept coming back to a single question:

‘Which route would allow someone to cross all seven bridges without crossing any of them more than once?’

 Ehler figured that it’s not possible. But attempting to explain why he wrote to Leonhard Euler (another famous mathematician) for help with the problem. Euler first dismissed the question as having nothing to do with math. But the more he wrestled with it, the more it seemed there might be something there after all. The answer he came up with had to do with a type of geometry that did not quite exist yet, what he called the Geometry of Position, now known as Graph Theory.

 Euler's first insight was that the route taken between entering an island or a riverbank and leaving it didn't actually matter. Thus, the map could be simplified (Illustration 2) with each of the four landmasses represented as a single point, what we now call a node, with lines, or edges, between them to represent the bridges. And this simplified graph allows us to easily count the degrees of each node. Degree is the number of bridges each land mass touches.

 These degrees matter because according to the rules of the challenge once travellers arrive onto a landmass by one bridge, they would have to leave it via a different bridge. In other words, the bridges leading to and from each node on any route must occur in distinct pairs. Implying  that the number of bridges touching each landmass visited must be even. The only possible exceptions would be the locations of the beginning and end of the walk.

Looking at the degrees in the Königsberg problem, it becomes apparent that all four nodes have an odd degree. So no matter which path is chosen, at some point, a bridge will have to be crossed twice.

Euler used this proof to formulate a general theory that applies to all graphs with two or more nodes.

 A Eulerian path that visits each edge only once is only possible in one of two scenarios:

1. The first is when there are exactly two nodes of odd degree – the starting and the end nodes – while the rest nodes have even degree. Example:

2. Second when all the nodes are of even degree. Then, the Eulerian path will start and stop in the same location, which also makes it something called a Eulerian circuit. Example:

It is fascinating how Euler approached a real world problem abstractly and formulated a solution framework which became foundation for graph database.