Answer to
old chestnut: houses and utilities:
Without cheating in the ways prohibited in the problem, it is impossible to solve this problem.
The reason is that the problem asks for the construction of a non-embeddable graph -- that is, a graph that cannot be drawn in a plane without intersections.
Graph theory is the study of graphs, sets of points with lines connecting some of the points. Graph theory states that there are two fundamental non-planar graphs: K(5), the complete graph for 5 points (like a pentagram including the outer pentagon connecting the five points of the star), and K(3,3), the complete bipartite graph with 3 points in each partition (the graph from the problem above). Any graph which contains one of these as a subset cannot be drawn in the plane without some lines intersecting, while any other graph can.
The proof that this is impossible is not difficult (the rest of the theorem above is considerably more difficult), and is based on Euler's Formula: F-E+V=2.
Here there are 6 vertices, V=6. There are 9 edges we want to draw, so E=9. That gives F = 5, 5 faces (including the "outside" face). Note that each face in this figure must have at least four edges (since each edge connects a house to a utility, but a two-edged face would require two lines from the same house to the same utility, and a three-edged face would require an edge between two houses or two utilities, neither of which we have included in our count). However, since each edge can only belong to two faces, 5 * 4 / 2 = 10 edges are required at minimum, and we have only drawn nine.