previous page: 186 geometry/kissing.number.p
page up: Puzzles FAQ
next page: 188 geometry/ladders.p

187 geometry/konigsberg.p


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?

             |   |   |   |
             |     |     |


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:

previous page: 186 geometry/kissing.number.p
page up: Puzzles FAQ
next page: 188 geometry/ladders.p