Haha...it is impossible mate. All this talk of graphs reminds me of a shit module called Program Analysis I did last year.
Anyway, the closest solution to connect the 3 X nodes and 3 Y nodes is with 8 edges. Which would leave one house without the supply of one ammenity (as you need 9 edges of the graph for the 6 nodes to all be interconnected and the puzzle solved, but you can't have 9 edges without an intersection.)
Even if you re-position the nodes it still can't be done. As shown here:
Basically, the only way to do this is in 3D or go through a house/supply.