previous page: 161 decision/truel.p
page up: Puzzles FAQ
next page: 163 geometry/bear.p

162 geometry/K3,3.p


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|

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:

previous page: 161 decision/truel.p
page up: Puzzles FAQ
next page: 163 geometry/bear.p