From: israel@math.ubc.ca (Robert Israel)
Newsgroups: sci.math
Subject: Re: Puzzle
Date: 1 Sep 1998 22:35:22 GMT

In article <35EC0F8B.24476127@orthopaedic-surgery.oxford.ac.uk>,
Daniel Derksen  <Daniel.Derksen@orthopaedic-surgery.oxford.ac.uk> wrote:

>I'm not sure if this is the right place to ask this question, but i'm
>gonna do it anyway,.. 

If you asked it is rec.puzzles, I think you'd be referred to their FAQ.

>The question is, is there a solution for this puzzle:


>    D      D      D       Draw a line from every O to every D
                          in such way that no lines intersect. 
>    O      O      O


>I think it is not possible, but I would like to see some kind of proof
>for it. Can anyone help me out ?

It's impossible, because the graph K_{3,3} is not planar.  Well, that's
really just a fancy way to say that your puzzle has no solution, so here's
a (somewhat informal) proof:

Number the vertices

     D1 D2 D3
     
     O1 O2 O3

First draw the lines D1  - O1 - D2 - O2 - D3 - O3 - D1.  This forms a 
simple closed curve which divides up the plane into an "inside" and an
"outside".  Each other line you draw must either stay inside or outside.
Now D1-O2 and D2-O3 can't both be inside and can't both be outside, so
one must be inside and the other outside.  However, the same goes for
the pairs [D3-O1 and D1-O2] and [D3-O1 and D2-O3].  So D3-O1 can't be
either inside or outside, and thus can't be drawn. 

Robert Israel                                israel@math.ubc.ca
Department of Mathematics        http://www.math.ubc.ca/~israel 
University of British Columbia            
Vancouver, BC, Canada V6T 1Z2
==============================================================================

From: gerry@mpce.mq.edu.au (Gerry Myerson)
Newsgroups: sci.math
Subject: Re: Puzzle
Date: Wed, 02 Sep 1998 11:18:40 +1100

In article <35EC0F8B.24476127@orthopaedic-surgery.oxford.ac.uk>, Daniel
Derksen <Daniel.Derksen@orthopaedic-surgery.oxford.ac.uk> wrote:

>     D      D      D       Draw a line from every O to every D
>                           in such way that no lines intersect. 
>     O      O      O

This is often stated as the Gas-Water-Electricity problem. You will find 
it solved in many introductory Graph Theory textbooks, where the picture 
may be referred to as K_3,3; look for Kuratowski in the index. 

One text of which I am particularly fond is Trudeau's Dots and Lines. 

Gerry Myerson (gerry@mpce.mq.edu.au)