From: Chris Cole <chris@questrel.com>
Newsgroups: rec.puzzles
Subject: Re: impossible or not
Date: Sat, 12 Jul 1997 12:15:06 -0700

G. van Uden wrote:
> 
> Hi there,
> 
> I got this one from my friend.
> 
> This is the problem a rectangle with 5 rectangles inside, 3 on top two on
> bottom.
> You must draw a single line, which snakes it way through each of the line
> segments, not crossing your own line or going through one of the
> rectangles' lines twice.
> This is exacly how my friend told it to me. Does anybody know this puzzle?
> 
> ___________________________________
> |           |          |          |
> |___________|__________|_________ |
> |                |                |
> |________________|_______________ |

This question is in the rec.puzzles archive:

==> 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.