Henry Ernest Dudeney/Puzzles and Curious Problems/261 - The Twenty-Two Bridges/Solution

Puzzles and Curious Problems by Henry Ernest Dudeney: $261$

The Twenty-Two Bridges

We have a rough map of a district with an elaborate system of irrigation,

as the various waterways and numerous bridges will show.

A man set out from one of the lettered departments to pay a visit to a friend living in a different department.

For the purpose of pedestrian exercise he crossed every one of the bridges once, and once only.

The puzzle is to show in which two departments their houses are situated.

Solution

$C$ and $L$.

Proof

Each department has an even number of bridges leading from it, except $C$ and $L$, which have $3$.

The underlying graph of this map is therefore traversable.

From Characteristics of Traversable Graph it follows that $C$ and $L$ are the start and end points.

Hence, for example:

$C, G, F, C, B, A, D, H, E, I, H, J, K, L, M, G, I, F, B, E, F, I, L$

$\blacksquare$

Sources

• 1932: Henry Ernest Dudeney: Puzzles and Curious Problems ... (previous) ... (next): Solution: $261$. -- The Twenty-Two Bridges
• 1968: Henry Ernest Dudeney: 536 Puzzles & Curious Problems ... (previous) ... (next): Answers: $419$. The Twenty-Two Bridges