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 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 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)