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."