3 Utilities | 3 Houses puzzle?

As others have pointed out, you are trying to find a planar representation of the complete bipartite graph $K_{3,3}$ and while there are many proofs that this is not possible, there is one that I find particularly neat.

We will rely on the following results:

1. $v-e+f=2$ for all planar graphs (see here)

2. bipartite graphs only contain cycles of even length (see here).

Proof: Let $G$ be a planar graph such that each cycle in $G$ is at least of length 4. Now, each face is just a cycle and since each cycle has at least 4 edges we can establish that $$\frac{4f}{2}\le e$$ whereas we divide by two to avoid double counting (every edge belong to two faces). Rearranging we get $$f\le\frac12 e$$ We can now use Euler's formula to arrive at an inequality that must be satisfied for all planar graphs with cycles of length at least length 4. $$\begin{align*} 2=v-e+f&\le v-e+\frac12e=v-\frac12e\\ \implies 2&\le v-\frac12e \\ \implies e&\le 2v-4 \quad (\spadesuit) \end{align*}$$ Now, in any graph, cycles can be no shorter than length 3 (this follows from the definition of a cycle). However, since $K_{3,3}$ is bipartite each cycle is even and so each cycle is at least of length 4$^*$. We can therefore use ($\spadesuit$) to see if $K_{3,3}$ is planar or not. $K_{3,3}$ has 6 vertices and 9 edges and so: $$9\nleq2(6)-4=8$$ It does not satisfy the inequality and so $K_{3,3}$ cannot be planar. Note that this shows what is so special about that last wire. If you only had 8 wires the inequality would be satisfied $$8\le2(6)-4=8$$

$^*$-Note for this problem you can actually check this for yourself by counting how many edges each cycle in $K_{3,3}$ has.

It's not hard to see this is impossible. Connect two houses to the three utilities, and you will essentially have a square with one diagonal drawn. The two corners joined are two of the houses, the other two corners and the midpoint of the diagonal are the utilities. (The actual shape may look distorted from this, but it is essentially this).

Where is the third house? If the house is "outside" the square, you cannot connect it to the utility in the middle. If the house is inside the square, then it is on one of the two sides of the diagonal, and therefore you cannot connect it to the vertex (utility) that is "across" the diagonal.

Postscript. As Aryabhata points out, I am implicitly using the Jordan curve theorem which says that a simple closed curve divides the plane into two disjoint regions, so that any path joining a point from the "outside" to a point "inside" has to cross the boundary. I use it when I argue that the house "outside" cannot be connected to the utility "inside" (without crossing the lines), or that you cannot go from one side of the diagonal to the other without crossing the diagonal.

In the language of Graph Theory, Graph $K_{3,3}$ is not a planar graph where $K_{m,n}$ is complete bipartite graph.

Definition of Planar Graphs is stated here .

Also as stated, "Kuratowski proved in $1930$ that a graph is planar iff it does not contain within it any graph that is a graph expansion of the complete graph $K_5$ or $K_{3,3}$."

In the book Amusements in Mathematics [4] [9], Henry Ernest Dudeney noted:

“There are some half-dozen puzzles, as old as the hills, that are perpetually cropping up, and there is hardly a month in the year that does not bring inquiries as to their solution. Occasionally one of these, that one had thought was an extinct volcano, bursts into eruption in a surprising manner. I have received an extraordinary number of letters respecting the ancient puzzle that I have called ‘Water, Gas, and Electricity’”.

As this interesting problem − which may be succinctly re-stated as “Can a planar graph be constructed from each of three nodes (‘houses’) to each of three other nodes (‘utilities’)?” [8] − “cropped up” on this website too, it seems profitable to list some references on the topic.

In particular, in response to the request of an intuitive easy to grasp (and almost maths-free) ‘proof’ that the graph $K_{3,3}$ is nonplanar, I would suggest going through Chris Lomont’s An Elementary Proof That The Utilities Puzzle Is Impossible [6].

References:

[1] Alexander Bogomolny, 3 Utilities Puzzle: Water, Gas, Electricity, in ‘Interactive Mathematics Miscellany and Puzzles’: http://www.cut-the-knot.org/do_you_know/3Utilities.shtml.

[2] John Adrian Bondy and U. S. R. Murty, Graph Theory With Applications, Elsevier Science Publishing, New York, 1976, pp. 144-145.

[3] Harold Scott MacDonald Coxeter, Self-dual configurations and regular graphs, in ‘Bulletin of the American Mathematical Society’ 56 (5), 1950, pp. 413-455.

[4] Henry Ernest Dudeney, Amusements in Mathematics, Thomas Nelson and Sons, London, 1917, pp. 73, 200-201.

[5] David Kullman, The Utilities Problem, in ‘Mathematics Magazine’ 52 (5), 1979, pp. 299-302.

[6] Chris Lomont, An Elementary Proof That The Utilities Puzzle Is Impossible, 2002: http://www.lomont.org/Math/Papers/2002/K33.pdf.

[7] Øystein Ore and Robin J. Wilson (editor), Graphs and their Uses, The Mathematical Association of America, Washington, 1990.

[8] Eric W. Weisstein, Utility Graph, in ‘MathWorld’ − A Wolfram Web Resource: http://mathworld.wolfram.com/UtilityGraph.html.

[9] David Wells, The Penguin Book of Curious and Interesting Puzzles, Penguin Books, New York, 1992, p. 101.

[10] Wikipedia contributors, Water, gas, and electricity, in ‘Wikipedia, The Free Encyclopedia’: http://en.wikipedia.org/w/index.php?title=Water,_gas,_and_electricity&oldid=623969177.