Puzzles/Geometric Puzzles/Connecting Utilities/Solution

Puzzles | Geometric puzzles | Connecting Utilities | Solution


This problem can be analyzed using graph theory.

The problem is essentially showing that the bipartite graph K3,3 is planar. However, Kuratowski's theorem tells us that this graph must not be planar.

Essentially, there is no solution and the required construction cannot be done! Sorry! :)

However, if we look at where the three houses and utilities are on a non-planar surface, such as a torus (or doughnut), we obtain some topological niceties that allow us to solve this problem.

Here is an example of one solution. Lines moving off the torus and looping around are signified with a V.

  \    | |  |    |      /  |     
 ==V===V=V==V====V=====V===V======
 : |   |  \  \   |    /    |     :
 : |  /-\' | |  /-\'  |   /-\'   :
 : |  |A|  | |  |B|   |   |C|    :
 : | ----- | | -----  |  -----   :
 : |__/ |  |  \_| |___/   | |    :
 :      |   \____________/  |    :
 :      \______     ________/    :
 :             \   /             :
 :              | |              :
 :    [G]---\   [W]       [E]    :
 :     | \  |    |       / | \   :
 ======V=V==V=====V=====V==V==V=== 
       | |  |    |     /   |   \


Here is a picture with forks, essentially equivalent to parallel connections


The solution usually given to this puzzle depends upon the fact that the puzzle, as stated, does not prohibit one of the connections going under a house (for example, the gas connection for A is routed G->pass under B->A). This appears to be topologically equivalent to the above(?).