Henry Ernest Dudeney/Modern Puzzles/158 - The Nine Bridges/Solution

Modern Puzzles by Henry Ernest Dudeney: $158$

The Nine Bridges

The diagram represents the map of a district with a peculiar system of irrigation.

The lines are waterways enclosing the four islands $A$, $B$, $C$, and $D$, each with its house,

and it will be seen that there are nine bridges available.

Whenever Tompkins leaves his house to visit his friend Johnson, who lives in one of the others,

he always carries out the eccentric rule of crossing every one of the bridges once, and once only,

before arriving at his destination.

How many different routes has he to select from?

You may choose any house you like as the residence of Tompkins.

Solution

Tompkins, and likewise Johnson, lives at either $B$ or $D$.

He has $132$ routes to choose from.

Proof

First we transform the map into a graph, by representing each island by a vertex and each bridge by an edge.

The outer mainland is represented by $E$.

The resulting graph is shown below.

It remains to count the number of different Eulerian trails.

This theorem requires a proof. In particular: if anyone out there isn't bored to tears by combinatorics You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by crafting such a proof. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{ProofWanted}} from the code. If you would welcome a second opinion as to whether your work is correct, add a call to {{Proofread}} the page.

Sources

• 1926: Henry Ernest Dudeney: Modern Puzzles ... (previous) ... (next): Solutions: $158$. -- The Nine Bridges
• 1968: Henry Ernest Dudeney: 536 Puzzles & Curious Problems ... (previous) ... (next): Answers: $415$. The Nine Bridges