(Close Window) 
Topic: Three houses three utility companies 


My nephew says it is possible, I say not. After years of trying your thoughts or access to solution...the object is to connect each house to each utility without crossing a line, you can go around but do not cross any lines: HHHH HHHH HHHH HHHH HHHH HHHH HHHH HHHH HHHH GGGG EEEE CCCC GGGG EEEE CCCC GGGG EEEE CCCC Thanks Jeff 


Okay to do this on the surface of a donut instead of a plane? 


I don't think it's possible, also this question bugged me for years. Some people said it's possible but they can't give a solution to it. 


It is actually quite easy to prove it is NOT possible—unless you allow the houses to have some physical size (i.e. not point size). Then one of the lines can go under one of the houses. N. 


No you are wrong it is possible,but how do I draw the answer on this page,mike 


Given only point size houses and point size utilities. it is NOT possible (it is called a 3,3 graph), given that we assume it is done on a flat page and each line leaves each utility to connect to a house DIRECTLY. if you need a proof of impossibility I'll either draw it or refer you to an internet link. if you assume that the houses have some "width" you can experiment a bit and see that there is a solution when one of the lines go under a house. N 


Make one of the houses solar powered. 


[quote] On 20040319 10:37, funemagic wrote: Make one of the houses solar powered. [/quote] LOL! Hey, a friend of mine gave me exactly that riddle a week ago at school. You can't imagine how fast history lessons can pass by.. However, I was getting crazy about this, because after about 2 minutes I told him it's impossible, and I KNEW it. (Now I know I don't know..) :) BTW.. another one from Nuernberg here. Small world, isn't it? :) 


Anyone got a citation for the proof? Is it a graph theory thing? 


It's not possible on a flat sheet of paper in a 2D drawing. It can be done with one sheet of paper but you need to fold a square piece of paper into a cube making a 3D plane to work on. On three sides draw the houses and the remaining 3 sides the utility companies. Now each house can receive 3 utility lines without crossing. A website I found gave a proof why it is not possible on a 2D plane then stated you would either a. draw a line through one of the houses (the directions do not say you can't cross through a house, just can't cross lines) or b. work it out on a 3D plane, thus the paper cube. 


I found that one on a german board: Falls Dich ein (sehr schoener) Beweis dafuer, dass man den Graph nicht zeichnen kann, interessiert, kannst Du ihn z.B. in Aigner/Ziegler: Proofs from the Book, Springer Verlag 2001 I'm Kapitel 10 nachschlagen. Now for the translation: If you are interested in a very nice proof, why you can't draw the graph, you may look at Aigner/Ziegler: Proofs from the Book, 2001 in chapter 10. AFAIK my library doesn't carry english books.. If one of you is interested in this, he can look for that book :) Greets, Alex 


[quote] On 20040322 14:31, Jonathan Townsend wrote: Anyone got a citation for the proof? Is it a graph theory thing? [/quote] http://www.cuttheknot.org/do_you_know/3Utilities.shtml 


The idea to apply Euler's equation for edges and faces and vertices eluded me. Thanks! 