This city of Königsberg, (now Kaliningrad, Russia) in Prussia as set on the river Pregel, and included two islands: Kneiphof and Lomse, connected by a single bridge. Lomse, the east-most island of the two, were connected to the north and south bank by a single bridge on each bank, while Kneiphof were connected by bridges on either bank.
During the first half of the 18th century, a popular problem among mathematicians in the city were to determine whether it was possible to traverse all bridges exactly once without jumping in the water. Swiss mathematician Leonhard Euler finally provided a general solution to the problem in 1736, laying the foundation to Graph-Theory in his paper published in Commentarii academiae scientiarum Petropolitanae, 1741.
In this short article, we will attempt to prove what Euler did - That the problem has no solution, using Neo4j.
Let's start by recreting the Bridge-problem graph:
CREATE
(a:ISLAND {name:'North Bank'}),
(b:ISLAND {name:'Kneiphof'}),
(c:ISLAND {name:'South Bank'}),
(d:ISLAND {name:'Lomse'}),
(a)-[ab:BRIDGE {name:'Krämer Brücke'}]->(b),
(b)-[ba:BRIDGE {name:'Schmeide Brücke'}]->(a),
(b)-[bc:BRIDGE {name:'Grüne Brücke'}]->(c),
(c)-[cb:BRIDGE {name:'Köttel Brücke'}]->(b),
(a)-[ad:BRIDGE {name:'Holz Brücke'}]->(d),
(b)-[bd:BRIDGE {name:'Dom'}]->(d),
(c)-[cd:BRIDGE {name:'Hohe Brücke'}]->(d)
RETURN a, b, c, d, ab, ba, bc, cb, ad, bd, cd;
Here we are giving all land-masses, including the banks the type ISLAND for simplicity.
Note that Neo4j requires all edges to have a direction. For our purposes, the direction of the edge is not important.
Next, let's try a few simple queries:
// How many islands are there?
$ MATCH (n:ISLAND) RETURN COUNT(n);
╒══════════╕
│"COUNT(n)"│
╞══════════╡
│4 │
└──────────┘
// How many bridges are there?
$ MATCH ()-[k]->() RETURN COUNT(n);
// What are the name of the bridges connected to the island Lomse?
$ MATCH (lomse:ISLAND {name: "Lomse"})-[k]-() RETURN k.name AS Bridge_Name;
╒═════════════╕
│"Bridge_Name"│
╞═════════════╡
│"Hohe Brücke"│
├─────────────┤
│"Dom" │
├─────────────┤
│"Holz Brücke"│
└─────────────┘
// What is the longest path between the two river-banks?
$ MATCH (nbank:ISLAND {name: "North Bank"})-[k*]-(sbank {name: "South Bank"}) RETURN LENGTH(k) AS len ORDER BY len DESCENDING LIMIT 1;
╒═════╕
│"len"│
╞═════╡
│6 │
└─────┘Before trying to solve the bridge-problem in Königsberg, let's try to create some simpler problems for ourselves. For the sake of clarity, we'll clear the database first. Be aware though - do this with the greatest sense of caution:
MATCH (n:ISLAND) DETACH DELETE n;Now we are ready to define the simples variant of the bridge-problem: Two island connected by a single bridge.
CREATE
(a:ISLAND {name:'A'}),
(w:ISLAND {name:'WORLD'}),
(a)-[k:BRIDGE]->(w)
RETURN *;
In our first simple bridge-problem, we have the two islands A and WORLD. The shape of our islands do not matter.
We will attempt to answer two very important questions:
// Can we start at A and end up at WORLD?
$ MATCH (a:ISLAND {name:'A'})-[k*]-(w:ISLAND {name:'WORLD'}) return COUNT(k) > 0;
╒══════════════╕
│"COUNT(k) > 0"│
╞══════════════╡
│true │
└──────────────┘
// Can we start at A, traverse all bridges exactly once then end up at A?
$ MATCH (a:ISLAND {name:'A'})-[k*]-(a) RETURN COUNT(k) > 0;
╒══════════════╕
│"COUNT(k) > 0"│
╞══════════════╡
│false │
└──────────────┘Of course it is possible to walk across the single bridge from A to WORLD. Also, since you can only cross the bridge once, you cannot walk across the bridge from A to WORLD, then return to A without teleportation.
Next, let's look at a similar problem with two bridges instead of one.
MATCH (w:ISLAND {name: "WORLD"})
CREATE (b:ISLAND {name:'B'}),
(b)-[k0:BRIDGE]->(w),
(w)-[k1:BRIDGE]->(b)
RETURN *;
Now try to ask the same questions again:
// Can we start at B and end up at WORLD by traversing each bridge exactly once?
$ MATCH (b:ISLAND {name:'B'})-[k*2]-(w:ISLAND {name:'WORLD'}) RETURN COUNT(k) > 0;
╒══════════════╕
│"COUNT(k) > 0"│
╞══════════════╡
│false │
└──────────────┘
// Can we start at B, traverse all bridges exactly once then end up at B?
$ MATCH (b:ISLAND {name:'B'})-[k*2]-(b) RETURN COUNT(k) > 0, COUNT(k);
╒══════════════╤══════════╕
│"COUNT(k) > 0"│"COUNT(k)"│
╞══════════════╪══════════╡
│true │2 │
└──────────────┴──────────┘Indeed, when starting at B, you would have to return to B in order to use both bridges connected to A, meaning that you will never end up at WORLD when starting at B.
Do note that there are two ways of traversing from B to B via WORLD, depending on which bridge you start with.
How about a bridge-problem with three bridges?
MATCH (w:ISLAND {name: "WORLD"})
CREATE (c:ISLAND {name: "C"}),
(c)-[k0:BRIDGE]->(w),
(w)-[k1:BRIDGE]->(c),
(c)-[k2:BRIDGE]->(w)
RETURN *;
// Can we start at C and end up at WORLD by traversing each bridge exactly once?
$ MATCH (c:ISLAND {name:'C'})-[k*3]-(w:ISLAND {name:'WORLD'}) RETURN COUNT(k) > 0, COUNT(k);
╒══════════════╤══════════╕
│"COUNT(k) > 0"│"COUNT(k)"│
╞══════════════╪══════════╡
│true │12 │
└──────────────┴──────────┘
// Can we start at C, traverse all bridges exactly once then end up at B?
$ MATCH (c:ISLAND {name:'C'})-[k*3]-(c) RETURN COUNT(k) > 0;
╒══════════════╕
│"COUNT(k) > 0"│
╞══════════════╡
│false │
└──────────────┘Once again we see that we may not end up at C if we started there. We instead end up at WORLD.
Do note that the number of paths from C to WORLD is double of what it should be. This is due to the ambiguity of our query, letting Neo4j choose our starting position.
So far, we have created four islands: A, B, C and WORLD, with WORLD being in the center:
With our small database of islands, we can start asking more intricate questions:
// Can we start at A and end up at C?
$ MATCH p=(a:ISLAND {name:'A'})-[*]-(c:ISLAND {name:'C'})
RETURN COUNT(p) > 0, COUNT(p), LENGTH(p);
╒══════════════╤══════════╤═══════════╕
│"COUNT(p) > 0"│"COUNT(p)"│"LENGTH(p)"│
╞══════════════╪══════════╪═══════════╡
│true │12 │4 │
├──────────────┼──────────┼───────────┤
│true │24 │6 │
├──────────────┼──────────┼───────────┤
│true │3 │2 │
└──────────────┴──────────┴───────────┘
// Can we start at A and end up at C when visiting B on the way?
$ MATCH p=(a:ISLAND {name:'A'})-[*]-(b:ISLAND {name:'B'})-[*]-(c:ISLAND {name:'C'})
RETURN COUNT(p) > 0, COUNT(p), LENGTH(p);
╒══════════════╤══════════╤═══════════╕
│"COUNT(p) > 0"│"COUNT(p)"│"LENGTH(p)"│
╞══════════════╪══════════╪═══════════╡
│true │6 │4 │
├──────────────┼──────────┼───────────┤
│true │24 │6 │
└──────────────┴──────────┴───────────┘
// Can we start at A and end up at C when not visiting B on the way?
$ MATCH p=(a:ISLAND {name:'A'})-[*]-(c:ISLAND {name:'C'})
WHERE NONE (b IN nodes(p) WHERE b.name='B')
RETURN COUNT(p) > 0, COUNT(p), LENGTH(p);
╒══════════════╤══════════╤═══════════╕
│"COUNT(p) > 0"│"COUNT(p)"│"LENGTH(p)"│
╞══════════════╪══════════╪═══════════╡
│true │3 │2 │
├──────────────┼──────────┼───────────┤
│true │6 │4 │
└──────────────┴──────────┴───────────┘
// Can we start at B and end up at C when visiting A on the way?
$ MATCH p=(b:ISLAND {name:'B'})-[*]-(A:ISLAND {name:'A'})-[*]-(c:ISLAND {name:'C'})
RETURN COUNT(p) > 0, COUNT(p);
╒══════════════╤══════════╕
│"COUNT(p) > 0"│"COUNT(p)"│
╞══════════════╪══════════╡
│false │0 │
└──────────────┴──────────┘
// Can we start at B and end up at A when visiting C on the way?
$ MATCH p=(b:ISLAND {name:'B'})-[*]-(c:ISLAND {name:'C'})-[*]-(a:ISLAND {name:'A'})
RETURN COUNT(p) > 0, COUNT(p), LENGTH(p);
╒══════════════╤══════════╤═══════════╕
│"COUNT(p) > 0"│"COUNT(p)"│"LENGTH(p)"│
╞══════════════╪══════════╪═══════════╡
│true │12 │4 │
└──────────────┴──────────┴───────────┘Here we see there is definitely a connection between all the islands. In addition we may observe that in order to traverse all the islands, we need to start or end at at A because this island only has a single bridge.
Somewhat surprisingly, we were able to start B and end up at A, visiting C on the way. However, when checking the length of the path taken between B and A, we notice that not all bridges were used.
From our queries, we may to start notice a pattern - that going to an island with an even number of bridges will end you up off the island after traversing all the bridges exactly once. When going to an island with an odd number of bridges will end you up on the island after traversing all the bridges exactly once.
The opposite is true when starting on an island with an even number of bridges. In this case, you will end up on the island after traversing all bridges exactly once, while going to an island with an odd number of bridges will end you up off the island.
This leaves us with this handy table:
| Starting on island | Starting outside island | |
|---|---|---|
| Odd number of bridges | We end up off the island | We end up on the island |
| Even number of bridges | We end up on the island | We end up off the island |
Going back to the bridges in Königsberg, recall that there are four islands, all with an odd number of bridges. We are free pick one of the islands to start, but since at least one of the other islands have an odd number of bridges, you need to end up there. But all the other islands have an odd number of bridges. This is a contradiction, meaning that the problem has no solution.
In short, it is impossible to have a walk, starting at any island, traversing all the bridges at least once.
Saving ourselves from all this fancy logic, we can actually solve this problem with a single query using Neo4j:
// Clean up database, be very carful using this
MATCH (n:ISLAND) DETACH DELETE n
WITH *
CREATE // Load database
(a:ISLAND {name:'North Bank'}),
(b:ISLAND {name:'Kneiphof'}),
(c:ISLAND {name:'South Bank'}),
(d:ISLAND {name:'Lomse'}),
(a)-[ab:BRIDGE {name:'Krämer Brücke'}]->(b),
(b)-[ba:BRIDGE {name:'Schmeide Brücke'}]->(a),
(b)-[bc:BRIDGE {name:'Grüne Brücke'}]->(c),
(c)-[cb:BRIDGE {name:'Köttel Brücke'}]->(b),
(a)-[ad:BRIDGE {name:'Holz Brücke'}]->(d),
(b)-[bd:BRIDGE {name:'Dom'}]->(d),
(c)-[cd:BRIDGE {name:'Hohe Brücke'}]->(d)
WITH *
MATCH ()-[k*]->() // Count the number of bridges
WITH COUNT(k) AS len
MATCH p=(a)-[*]-(b) WHERE LENGTH(p)=len RETURN COUNT(p) > 0, COUNT(p);
╒══════════════╤══════════╕
│"COUNT(p) > 0"│"COUNT(p)"│
╞══════════════╪══════════╡
│false │0 │
└──────────────┴──────────┘Q.E.D.