Graph model and Neo4j — where data is designed around relationships

Königsberg bridge problem

Can one find out whether or not it is possible to cross each bridge exactly once?

In the 18th century, the Swiss mathematician Leonhard Euler was intrigued by the question of whether a route existed that would traverse each of the seven bridges exactly once. In demonstrating that the answer is no, he laid the foundation for graph theory. (Source: Encyclopedia Britannica)

This famous question from the 18th century, about seven bridges connecting two small islands over Pregel river (a small town Königsberg, today’s Kaliningrad, Russia) became the foundation of Graph Theory. This question provoked the curiosity of Swiss mathematician Leonhard Euler; he was obsessed with finding a mathematical solution to this problem.

The key to this problem is understanding the degree of each node (how many bridges are connected to each landmass). In order to meet the rule (one can travel over each bridge only once), there should be a distinguished path which one can take to leave a node, as long as there is a path which one can take to arrive to this node. In other words, paths connecting to each node should always make up a pair, one for arriving and another one for leaving, hence the degrees of each node must always be an even number. The only exceptions are nodes at the very beginning and end of the entire path.