## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 187 geometry/konigsberg.p

Can you draw a line through each edge on the diagram below without crossing

any edge twice and without lifting your pencil from the paper?

+---+---+---+
| | | |
+---+-+-+---+
| | |
+-----+-----+

geometry/konigsberg.s

This is solved in the same way as the famous "Seven Bridges of

Konigsberg" problem first solved by Euler. In that problem, the task

was to find a closed path that crossed each of the seven bridges of

Konigsberg (now Kaliningrad, Russia) exactly once. For reasons given

below, no such path existed. In this version, you cannot draw such a

line without cheating by:

(1) drawing a line along one of the edges, or

(2) inscribing the diagram on a torus, or

(3) defining a line segment as the entire length of each straight line, or

(4) adding a vertex on one of the line segemnts, or

(5) defining "crossing" as touching the endpoint of a segment.

The method for determining if paths exist in all similar problems is

given below.

Turn each "room" into a point. Turn each line segment into a line

connecting the two points representing the rooms it abuts. You should

be able to see that drawing one continuous line across all segments in

your drawing is equivalent to traversing all the edges in the resulting

graph. Euler's Theorem states that for a graph to be traversable, the

number of vertices with an odd number of edges proceeding from them

must be either zero or two. For this graph, that number is four, and it

cannot be traversed.

+---+---+---+
| 1 | 2 | 3 |
+---+-+-+---+ 6 (outside)
| 4 | 5 |
+-----+-----+

Number of edges proceeding from each vertex:

1: 4
2: 5 (*odd*)
3: 4
4: 5 (*odd*)
5: 5 (*odd*)
6: 9 (*odd*)

To prove Euler's Theorem, think of walking along the graph from vertex to

vertex. Each vertex must be entered as many times as it is exited, except

for where you start and where you end. So, each vertex must have an

even number of edges, except possibly for two vertices. And if there are

two vertices with an odd number of edges, the path must start at one and

end at the other.

Continue to: