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.

lib/DbaDatabase.php:134: Warning: dba_replace() [<a href='function.dba-replace'>function.dba-replace</a>]: You cannot perform a modification to a database without proper access