# Graph or combinatorics proof to my concern to a water, gas, electric, puzzle? [duplicate]

Possible Duplicate:
3 Utilities | 3 Houses puzzle?

A man has built three houses. Nearby there are gas water and electric plants. The man wishes to connect all three houses to each of the gas, water and electricity supplies.

Unfortunately the pipes and cables must not cross each other. How would you connect each of the 3 houses to each of the gas, water and electricity supplies

My concern is: If pipes and wire cannot cross with house and stations, then how to prove a solution does not exist by graph theory or combinatorics?

link to the original problem: http://puzzles.nigelcoldwell.co.uk/twentysix.htm

-

## marked as duplicate by Mike Spivey, 5PM, Davide Giraudo, draks ..., Hagen von EitzenJan 19 '13 at 22:21

The short graph theory proof is: The graph $K_{3,3}$ is not planar. –  Hagen von Eitzen Jan 19 '13 at 16:28