Connect the three houses to the three utilities without crossing paths.

Proof One. A beauty sent by John Conway. The following cycle exists in the graph: (1 W 2 G 3 E).

Proof Two. Euler proved that connected planar graphs satisfy the following important relation:

Proof Three, sent to me by Richard Guy. Again, use Euler's formula, then note that K(3,3) is bipartite, so that any region in a drawing without crossings has an even number of edges, hence at least 4. The five faces have at least 20 edges. Each edge may be shared by two faces, so at least 10 edges are in the graph. But the graph has 9 edges -- contradiction.

With tricks, the Water-Gas-Electricity problem can be solved. Just run a line under one of the houses.

Joseph DeVincentis had the following comments:

"There's a problem on your page this week with Proof Two for why

the W-G-E problem has no solution.

The 9 cycles you describe in this proof are not necessarily

"faces" per the definition used in Euler's formula. Some

of them could exist but have other points both inside and

outside of them.

For instance, take Conway's diagram from proof 1 and connect

3 to W inside the loop and 2 to E outside. This diagram has

five of these "faces" even though it only has eight edges.

Four of these (1W3E, 2W3G, 2G3E, and 2W1E) are actual faces

(the last of them being the "outside" face), but 2W3E cannot

be considered a face by any means."