**From New Scientist #2497, 30th April 2005**

The picture shows villages A to K and all but one of the lanes between them. The missing lane does not cross any other lane.

I remember that it is possible to reach a friend’s village by starting at my village, going for a walk along the lanes, and using every lane exactly once.

I also remember that it is possible to start at my village, go for a walk along the lanes, and pass though each of the other villages exactly once before returning to my own village.

Which two villages are joined by the lane which was missed out of the picture?

[enigma1338]

### Like this:

Like Loading...

A path that visits each edge of the graph exactly once is known as a Eulerian Path [ http://en.wikipedia.org/wiki/Eulerian_path ]. In order for such a path to exist the start and end vertices must have odd degree, and the remaining vertices must have even degree. (Or if the start and end vertices are the same all vertices must have even degree).

A path that visits each vertex of the graph exactly one and returns to the starting vertex is known as a Hamiltonian Circuit [ http://en.wikipedia.org/wiki/Hamiltonian_path ].

This Python program considers the graph given in the diagram and adds an extra edge to see if that produces a graph with exactly two vertices of odd degree. If so it looks for a Eulerian Path on the graph, and a Hamiltonian Circuit.

It’s a Python 3 program (as it uses the

yield from ...construct) and runs in 68ms.Solution:The lane missing from the map joins I and K.The home villages are F and J, but we don’t know which is which as the path can be traversed in either direction (F to J or J to F), and the circuit can start and end at any node.