AN ELEMENTARY PROOF THAT THE UTILITIES PUZZLE IS IMPOSSIBLE

CHRIS LOMONT

Abstract. The Utilities Puzzle requires connecting each of three utilities X, Y, and Z to the three houses A, B, and C, without crossing pipes. It is equivalent to the graph K_{3,3} being nonplanar. Here I present a simple proof that can convince even most nonmath majors.

1. The Utilities Puzzle

The Utilities Puzzle is: There are three houses A, B, and C, and three utilities (gas, electric, water) labelled X, Y, and Z. Mark the houses and utilities as points in the plane. Find a way to connect each of the utilities with each house, without crossing any lines.

My brother showed this puzzle to me while I was in middle school and he was in high school. For years he doodled with it to pass time in meetings, until I reached grad school, and saw a proof that the graph K_{3,3} is non-planar. My brother was upset when I told him the problem is impossible, but unfortunately I could not explain the proof, since it used results in graph theory. Recently another friend showed me this problem, to which I replied it was unsolvable, but this time I tried to prove it to his liking, and found this rather basic proof that the problem has no solution. Here is the reasoning:

Suppose there is a solution drawn on a rubber sheet with curves connecting AX, AY, AZ, BX, BY, BZ, CX, CY, and CZ, none of which cross except at the endpoints:

[figure: A; B; C; X; Y; Z; ?]

Then, just using B, X, Y, and Z, and the connecting curves BX, BY, and BZ, the rubber sheet can be stretched to give:

[figure: B; X; Y; Z]

Then the rubber sheet can be stretched, placing the house C and the curve CY like:

[figure: C; B; X; Y; Z]

Now for the hardest part to see: The curve CZ can be stretched into one of two cases. The leftmost picture (case 1) is clearly one such curve, but it takes some thinking to convince oneself that the rightmost picture (case 2) is the only other possible curve CZ. One way to reason is that the loop BY CZ either encloses X or it does not.

[figure: C; B; X; Y; Z]
[figure: C; B; X; Y; Z]

Consider the right case. There must be a curve CX, and the only possibility is that it can be deformed to give:

[figure: C; B; X; Y; Z; II; I; III]

Then the house A must be in one of the regions I, II, or III. If A is in region I it cannot be connected to utility Y by a curve that does not cross any other curve. If A is in II, it cannot connect to Z, and finally if A is in region III, it cannot be connected to X.

So we are left with case 1 only. Stretching the curve CX, we get two cases again (by the same reasoning above - only two curves are possible determined by whether or not Z is inside the loop BY CX):

[figure: C; B; X; Y; Z; II; I; III]
[figure: C; B; X; Y; Z; II; I; III]

Place house A on the left diagram. If it is in region I, it cannot connect to Y, if A is in II, it cannot connect to Z, and if A is in region III, it cannot connect to X. The same sentences apply to the right diagram.

Thus all cases have been studied, and the Utilities Puzzle has no solution in the plane. Equivalently the graph K_{3,3} is non-planar.

Department of Mathematics, Purdue University, West Lafayette

Indiana 47907 Email address: clomont@math.purdue.edu First written: Nov 2002