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?

I think I may need another cup of coffee before I properly comprehend that.

ReplyDeleteI mostly dislike math. Don't ask me how it ended up in my novel...

Wow! Yeah, my head hurts. But I did read the post until the end. I am actually interested enough to go back and now try to understand it.

ReplyDeleteI think you lost me...

ReplyDeleteIn theory I am a math lover but in practice I get lost a lot but your analysis is very impressive.

ReplyDeleteMeet My Imaginary Friends

#AtoZchallenge http://www.kathleenvalentineblog.com/

I'm a math-tolerator. :)

ReplyDeleteMath lover here! And I have a goal of seeing old bridges in Europe and take a few selfies on them.

ReplyDeleteOh dear, my brain is fried, but due to minor surgery today, right now nothing is making sense. But still, I'm not a math person, but walker, oh yeah. I'll just take the most scenic route and if I cross more than once I won't mind! LOL

ReplyDeleteIf "followed" means I read it to the end, then I followed it to the end. But if it means I UNDERSTOOD it till the end ... then I guess my ruse is up. I just heard a couple synapses explode. Ouch.

ReplyDeleteI don't think I'd ever be able to figure that one out on my own!

ReplyDeleteWelcome to My Magick Theatre

Onomastics Outside the Box

I can see your mathematician side :) I think I get it. I was really good at math in school to a point that I got bored with it. I did come back around in college with an elementary teaching math class which was a lot of fun!

ReplyDeleteI always liked maths, but my brain is currently going 'duh, what?' :) I think I need to come back when I have my brain in gear, or maybe that is just a faint hope ;)

ReplyDeleteTasha

Tasha's Thinkings | Wittegen Press | FB3X (AC)

My brain hurts.

ReplyDeleteHeather

20160707meiqing

ReplyDeletejordan pas chermichael kors outlettrue religion outletmichael kors outlet onlinenike huarache trainersair max 2016abercrombie and fitch outletburberry outlet onlinemichael kors outletmichael kors outlet storehermes ukabercrombie and fitchmichael kors outletnorth face jacketsjimmy choo shoesoakley sunglassesversace sunglasseslongchamp outletadidas nmd whiteoakley sunglassesarmani watchesthe north faceadidas superstarsupra for saleconverse trainerscoach outletchristian louboutintrue religion outletcoach outletlouis vuitton outletray ban sunglasses discountmichael kors outleted hardy ukhugo boss outlethollister clothingcartier watcheskobe 9

ReplyDeleteadidas stan smith womenkobe 9hermes beltmichael kors handbagsadidas superstarnike poloadidas nmdnike air max 90falcons jerseylacoste online shop