# Königsberg bridge problem complexity estimate

I'm having fun reading the "Königsberg bridge problem" and the Euler story.

I read that if we make the assumption that for every node of the graph starts 2 paths, a rough estimate for the number of possible walks in the graph would be $2^{7}$, since 7 is the number of bridges. But i dont understand why.

I think that it can be proved using a tree, but i dont know how do it. What im asking if how practically derive the rought estimate of $2^{7}$ using a tree. Can you help me ?

• I don't see how to reach that number. The number of possible paths has to be higher. If the 4 nodes would have 3 exiting bridges each, the number of paths would be 3^7 (since at every step you would have 3 possibilities, so 3*3*3*3*3*3*3). But this number is even bigger, since of the the nodes has 5 possible exits – Ripstein Mar 21 '18 at 16:56

Step 1: Make each land max a vertex (blue circle in the image below)
Step 2: Make each bridge an edge (black lines connecting the blue circles) You can see there's 7 edges.
Each of these edges (bridges) can only be used once, so let's label them 1 if used in the walk and 0 if not used.

Some examples of walks are then:
0000000 (you don't walk anyway, just stand on the vertex on which you started)
1111100 (you use the first 5 bridges, but the last two bridges don't get used)
1011111 (6 of the edges are used, but one is left not used).

How many strings of length 7 can you make with just 0's and 1's ?
The answer is 7 because there's 2 possibilities for position 1, for each of those possibilities there's 2 possibilities for position 2, for each of those there's 2 possibilities for position 3, etc. The total number of walks would then be $$2\times2\times2\times2\times2\times2\times2 = 2^7$$.

Now if you care about the order in which these bridges are used, then the string: 1111100 (where the 0's are only for the bridges at the extreme left) can be achieved in many different ways, depending on which vertex you start on and which order you take the bridges in order to use these 5 bridges. This might be why the comment says that the number of walks is larger then $$2^7$$.

However you are partially correct in that $$2^7$$ gives you an upper bound on the total number of possible unique paths that can be used, where by "unique" I mean two walks involving the exact same set of bridges are counted as being the same (because that's what matters for the 7 bridges of Konigsberg problem anyway).

You have probably found out already that the path: 1111111 is impossible under the rules of the problem. So in fact $$2^7$$ is just an upper bound on the number of assignments to the bridges as "used" and "not used".

I have therefore told you the only way that the $$2^7$$ can arise, but I've also explained why it is not the actual number of "walks" that can be made, since you can get 1111100 in more than one different way.