Three houses, three utilities, no crossing pipes

Question

Three houses each need connecting to three utilities: gas, water and electricity. Each house must have its own line to each utility, nine lines in all, drawn on flat ground, and no two lines may cross.

Show that it is impossible, and explain what a proof of impossibility has to look like. Would it be possible on the surface of a doughnut?

Accepted Answer

Impossible in the plane. Possible on a torus. Euler's formula. Any connected drawing in the plane with no crossings satisfies V minus E + F = 2, where V is the number of vertices (here the 3 houses and 3 utilities, so V = 6), E the number of edges (the 9 lines), and F the number of regions the drawing cuts the plane into, counting the outside. If the drawing existed, F would be 2 minus 6 + 9 = 5. Every region has at least four sides. Walk around the boundary of any region. Lines only join a house to a utility, never house to house or utility to utility, so the boundary alternates house, utili…

Three houses, three utilities, no crossing pipes

Your answer

Discussion

Learn the concepts

Related questions