The Three Utilities Puzzle: Why Six Simple Connections Are Impossible on a Flat Page

The Puzzle That Looks One Line Away

Draw three houses and three utility stations—water, gas, and electricity. Each house needs its own connection to every utility, and no two lines may cross. It sounds like a test of careful drawing. In fact, it is impossible on a flat page: the six marked points require nine connections, and their arrangement cannot be drawn without a crossing.

That distinction matters. The “six” in the title refers to the three houses and three utilities, not the number of lines you must draw. Each of three houses needs three lines, making (3 \times 3 = 9) connections altogether.

If you have a pencil nearby, give it a try before reading on. You can place the houses and stations anywhere, and your lines may curve as much as you like. Keep each connection separate, though: a line cannot pass through an unrelated house or station, and lifting the pencil over another line does not count.

Why the Ninth Line Causes So Much Trouble

Many attempts get tantalizingly close. You connect one house to all three utilities, then do the same for a second. Perhaps you weave several more lines through the gaps. Soon, eight connections are in place—and the ninth seems as though it ought to fit.

Moving a house does not fix it. Neither does drawing a longer curve or taking a line far around the outside. The obstacle is not a cramped patch of paper; it is the pattern of which points must connect. A graph-theory lecture from Gresham College’s discussion of the utilities puzzle notes that eight connections can be drawn without crossing, but all nine cannot.

That makes this an unusual puzzle. Usually, reaching “almost solved” means you should rethink your last move. Here, it is a clue that the rules themselves block the finish. Puzzles Arcade’s account of the impossible 15-puzzle arrangement explores a similar surprise: a goal can look close while remaining unreachable by legal moves.

Turn the Drawing Into a Graph

Mathematicians call the houses and utilities vertices, and the lines between them edges. They are interested in the connections, not whether you drew a house as a square or a dot.

The three houses form one group; the three utilities form another. Every house connects to every utility, but houses do not connect to houses, and utilities do not connect to utilities. This pattern is called the complete bipartite graph (K_{3,3}). “Bipartite” means its vertices split into two groups; the two 3s tell us that each group has three vertices.

A graph is planar if it can be drawn on a flat surface without its edges crossing, except where they meet at a shared endpoint. You are allowed to rearrange the vertices and bend the edges. If even one crossing is unavoidable after all that freedom, the graph is nonplanar. The utilities puzzle asks whether (K_{3,3}) is planar. It is not.

A Picture-Based Reason It Cannot Work

Imagine drawing six of the connections as a closed loop. You can alternate houses and utilities around it:

House A → Water → House B → Gas → House C → Electricity → House A

That loop uses all six marked points and leaves three house–utility connections to add. For now, picture the loop as a hexagon. It has an inside and an outside, and each remaining connection must travel on one side or the other without crossing the loop.

Here is the catch: the endpoints of any two remaining connections alternate as you travel around the loop. If you draw those two connections on the same side, they must cross. Picture four points around the rim of a circle: a line joining the first and third cannot avoid a line joining the second and fourth when both stay inside. The same reasoning works outside the loop.

There are three connections left but only two sides of the loop. At least two connections must go on the same side, where they cross. Making the loop wobbly, changing its size, or curving the remaining lines does not remove that conflict. This is a way to prove the puzzle impossible, rather than merely reporting that no one has found a tidy drawing.

The Surprising Arithmetic Behind the Drawing

There is a second proof for anyone who enjoys seeing a picture turn into numbers. For a connected graph drawn without crossings on a flat plane, Euler’s formula says:

[ V-E+F=2 ]

Here, (V) counts vertices, (E) counts edges, and (F) counts the regions—called faces—made by the drawing. The large region outside the drawing counts as a face too. An accessible explanation appears in Discrete Mathematics: An Open Introduction’s section on planar graphs.

Suppose, just for a moment, that all nine utilities connections could be drawn without crossings. They would give us six vertices and nine edges. Euler’s formula would then require:

[ 6-9+F=2,\qquad\text{so}\qquad F=5. ]

Now count the edges around those five supposed faces. Each face would need a boundary of at least four edges. Why not three? Because every edge runs between a house and a utility. A trip along the edges must alternate between those two groups, so it cannot return to its starting point in three steps. Five faces would therefore need at least (5 \times 4 = 20) edge-sides between them.

But nine edges offer only (9 \times 2 = 18) edge-sides: each edge borders two sides of faces. The same drawing cannot require at least 20 and provide only 18. Our imaginary crossing-free drawing is impossible. The arithmetic catches the very obstacle that the loop makes visible.

Can You Change the Rules and Make It Work?

Yes—and that helps pinpoint what the puzzle actually says. In a real neighborhood, a pipe could go beneath a cable, or one connection could travel over another on a bridge. They might cross in a drawing viewed from above without meeting in three-dimensional space. That is a practical solution, but it is no longer a crossing-free drawing on one flat surface.

A surface with a hole changes things more dramatically. Wolfram MathWorld’s entry on the utility graph shows that (K_{3,3}) can be drawn without crossings on a torus—a doughnut-shaped surface. The familiar impossibility belongs to the plane, not to every surface imaginable.

You could also change the task by dropping one required connection. Then the eight-line version can be drawn without crossings. But if every house still needs all three utilities on a flat page, the missing ninth line cannot be wished away.

The Real Feat Is Knowing When to Stop Drawing

The three utilities puzzle rewards curiosity at every stage. Drawing teaches you how easily eight lines can fit. The loop reveals why the remaining lines compete for space. Euler’s formula confirms the problem with a short, decisive count.

Its lesson reaches beyond this one page: sometimes persistence means trying another arrangement, and sometimes it means asking whether an arrangement can exist at all. That is also the appeal of Euler’s 36 officers puzzle, another challenge whose restrictions are the heart of the story. For the three utilities, a crossing is not a failure of imagination. Discovering why it is unavoidable is the amazing feat.