## Description

This article is from the Puzzles FAQ,
by Chris Cole chris@questrel.questrel.com and Matthew Daly
mwdaly@pobox.com with numerous contributions by others.

# 162 geometry/K3,3.p

Can three houses be connected to three utilities without the pipes crossing?

_______ _______ _______
| oil | |water| | gas |
|_____| |_____| |_____|
_______ _______ _______
|HOUSE| |HOUSE| |HOUSE|
| one | | two | |three|
geometry/K3,3.s

The problem you describe is to draw a bipartite graph of 3 nodes

connected in all ways to 3 nodes, all embedded in the plane. The graph

is called K3,3. A famous theorem of Kuratowsky says that all graphs

can be embedded in the plane, EXCEPT those containing a subgraph that

is topologically equivalent to K3,3 or K5 (the complete graph on 5

vertices, i.e., the graph with 5 nodes and 10 edges). So your problem

is a minimal example of a graph that cannot be embedded in the plane.

The proofs that K5 and K3,3 are non-planar are really quite easy, and

only depend on Euler's Theorem that F-E+V=2 for a planar graph. For

K3,3 V is 6 and E is 9, so F would have to be 5. But each face has at

least 4 edges, so E >= (F*4)/2 = 10, contradiction. For K5 V is 5 and

E is 10, so F = 7. In this case each face has at least 3 edges, so E >=

(F*3)/2 = 10.5, contradiction.

The difficult part of Kuratowsky is the proof in the other direction!

A quick, informal proof by contradiction without assuming Euler's Theorem:

Using a map in which the houses are 1, 2, and 3 and the utilities are

A, B, and C, there must be continuous lines that connect the buildings and

divide the area into three sections bounded by the loops A-1-B-2-A,

A-1-B-3-A, and A-2-B-3-A. (One of the areas is the infinite plane *around*

whichever loop is the outer edge of the network.) C must be in one of these

three areas; whichever area it is in, either 1, or 2, or 3, is *not* part of

the loop that rings its area and hence is inaccessible to C.

The usual quibble is to solve the puzzle by running one of the pipes

underneath one of houses on its way to another house; the puzzle's

instructions forbid crossing other *pipes*, but not crossing other *houses*.

Continue to: