Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The Seven Bridges Of Konigsberg !

  1. Mar 19, 2005 #1
    Hello Everyone,

    I was trying to solve couple of fun problems. Many of you must have heard about the famous The Seven Bridges Of Konigsberg and how Euler solved the puzzle. You can do a quick google...

    Here is a diagram if you want it...
    http://www.contracosta.cc.ca.us/math/BridgeGraph.GIF [Broken]

    One of the question is:
    1) Can you walk from say point B to point A crossing each bridge exactly once.
    Answer - This is an Euler path problem. So question can be thought of as: Is there an Euler path from point B to A. Well, B has 5 degrees and A has 3 degrees so start and end points are odd degree but the other points (namely, C and D) are odd . This violates Euler's path definition. So it is not possible.

    Is my reasoning correct? :confused:

    2) If I am moving from C to B and I must cross each bridge atleast once. what is the minimum number of times I have to cross a bridge?
    Answer - Is tracing with the pencil the best way to do this problem. I got 8.

    Please respond as soon as possible. Thank You for your time.
    Last edited by a moderator: May 1, 2017
  2. jcsd
  3. Mar 19, 2005 #2
    For 1, your conclusion is correct, but your answer is sort-of "fuzzy". I'd answer that question by saying "An Euler path is (you fill in the definition), so this question is asking if there is (...)." Then you can continue by telling what condition is necessary and sufficient for a connected multigraph to have an Euler path. Finally, draw your conclusion by applying that theorem to the particular graph you are dealing with.

    For 2, I don't know of any better way. And you already know the answer can't be 7, so if you can show a path crossing 8 edges, what could be better?
  4. Mar 19, 2005 #3
    Kool. Thanks a lot gnome !
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook