Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: Notesfiles; site ea.UUCP
Path: utzoo!watmath!clyde!burl!mgnetp!ihnp4!inuxc!pur-ee!uiucdcs!ea!mwm
From: mwm@ea.UUCP
Newsgroups: net.puzzle
Subject: Re: Don't cross my path ! - (nf)
Message-ID: <10200003@ea.UUCP>
Date: Fri, 17-Aug-84 17:47:00 EDT
Article-I.D.: ea.10200003
Posted: Fri Aug 17 17:47:00 1984
Date-Received: Wed, 29-Aug-84 05:31:05 EDT
References: <785@abnjh.UUCP>
Lines: 30
Nf-ID: #R:abnjh:-78500:ea:10200003:000:1345
Nf-From: ea!mwm    Aug 17 16:47:00 1984

#R:abnjh:-78500:ea:10200003:000:1345
ea!mwm    Aug 17 16:47:00 1984

/***** ea:net.puzzle / convex!graham / 10:14 am  Aug 16, 1984 */
This seems to be the same as the three houses, three tanks (water, gas, oil)
problem: run pipes from all tanks to all houses without crossing pipes.
I believe that planar graph theory can be used to show that it is impossible,
though I can't give the proof.

Marv Graham; Convex Computer Corp. {allegra,ihnp4,uiucdcs,ctvax}!convex!graham
/* ---------- */

You are right, and wrong. The 3 houses/3 tanks problem calls for K\-{3,3}
(see below) which is not planar. The proof is to long to post. Try looking
in Harary's _Graph Theory_, under Kuratowski's theorom (pg 108 in my copy).
The graph for the 3 houses/3 doors problem is 3 * K\-2 (see below), which
*is* planar. The solution to the problem is straight forward after you
realize that.

		<mike

K\-{3,3} is the complete bigraph on two pairs of 3 points. The \-{3,3} is a
TeX-like notation for subscripting. To see what K\-{3,3} looks like, draw
two lines of three points, about an inch apart. Now, from each point in the
left set of points draw a line to each point in the right set, for a total
of nine lines. Note that you will not be able to draw all nine lines without
one crossing another, unless you have 3d paper.

3 * K\-2 is the three copies of the complete graph on two points. In other
words, three line segments.