Problem 10
Can you draw a continuous curve that passes through each of the 16 line segments in the figure below exactly once? Why or why not?
A curve that goes through a vertex is not allowed.
Solution
We can model each region of the first figure as a node in a graph.
For every edge
e that separates regions
x and
y in the above figure, an edge xy links their corresponding nodes in the graph. The task of drawing a curve that passes through each of the 16 line segments has now been transformed into the problem of finding a Euler path in the graph (A path that traverses each edge of the graph once). This type of path can only exist if there are no more then two nodes with an odd degree. (Each in-edge to a node must have a corresponding out-edge, unless the node is the origin or end of the Euler path).
