Source: Scottish Bridge by Judit Bermudez Morte
Königsberg Bridge. The town of Königsberg (now Kaliningrad) is in Russia. Königsberg had seven bridges joining the two sides of the river and also an island and a peninsula. (Source: Gates, Les Bill. "Activity: The Seven Bridges of Königsberg" Math Is Fun. Ed. Rod Pierce. 24 Jan 2014. 12 Apr 2016 http://www.mathsisfun.com/activity/seven-bridges-konigsberg.html) This is also the source for the following three images.)
Mathematician Leonhard Euler was asked if it was possible to walk through Königsberg, visit each part, and cross each bridge only once. (You can visit city "parts" more than once.)
In order to made the problem easier, we use Graph Theory. First we simplify the picture, labeling each part of town with a capital letter (A, B, C, and D) and each bridge with a lower case letter (p, q, r, s, t, u, v):
Otay! Now grab a stylus and get walking. Let's try the path A-p-C-r-B-s-C-q-A-u-D-v-B oh crap, we would have to cross bridge r or s or v to get to bridge t. Try a few more routes and you'll get the feeling such a walk is not possible. That is correct. Why not?
Let's change the picture a bit more, representing each part of the city with a dot (called a vertex in graph theory) and each bridge with a line (called an edge in graph theory). The resulting picture is called a graph. A path that passes through each edge (bridge) exactly once is an Euler path.
It looks like a pair of dropped ice-cream cones, doesn't it? This problem would be much easier if the bridges labeled q, s, and t disappeared. Then we could merrily go in a simple circle A-p-C-r-B-v-D-u- and be back at A. Done and done. Or add another bridge, say bridge w between B and C. Then our first attempt could be completed as: A-p-C-r-B-s-C-q-A-u-D-v-B-w-C-t.
Now let me throw another graph theory definition at you: the degree of a vertex (dot) is the number of edges next to that vertex. Since A is next to bridges p, q, and u, its degree is 3 or d(A)=3. Similarly, d(B)=3, d(C)=5, and d(D)=3.
If we took away bridges p, q, and t, the degrees would be d(A)=2, d(B)=2, d(C)=4, and d(D)=2.
So does the Euler path only exist if the degrees are all even? Not quite.
If we added our bridge w between B and C, the degrees would be d(A)=3, d(B)=4, d(C)=6, and d(D)=3, and our Euler path (A-p-C-r-B-s-C-q-A-u-D-v-B-w-C-t) does exist.
So what's up? The solution is this: A graph has an Euler path if there are no vertices with an odd degree or two vertices with an odd degree.
Ta-DAH! Extra gold star if you followed this blog to the end. Are you a math hater, tolerator, or lover?