# 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 K_{3,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(?).