The Three Utilities Puzzle

Where’s the maths? This is graph theory — and, hiding just behind it, topology, the mathematics of what stays true when you bend and stretch a shape. Six dots and nine lines is all this puzzle is: three houses, three utilities, one pipe for every house–utility pair. Nothing about the answer depends on where you put the houses or how curvy you make the pipes, so the real question is not a drawing question at all — it is a question about the surface you are drawing on. A picture drawn on a flat sheet with no lines crossing is called a planar drawing, and it obeys a hard counting law discovered by Euler in 1750. That law says a flat drawing with 6 dots and 9 lines must cut the sheet into exactly 5 pieces — and then a second count shows 5 pieces is one piece too many to be possible. So the puzzle is not hard; it is impossible, and you can prove it with nothing but counting.

Call the dots V, the pipes E and the regions the drawing cuts the sheet into F (counting the endless region outside everything as one face). Euler’s formula for any connected drawing with no crossings is V − E + F = 2.

• Here V = 6 and E = 9, so if a crossing-free drawing existed it would have F = 2 − 6 + 9 = 5 faces. No choice about it.
• Now bound the faces from below. Every pipe joins a house to a utility, so walking round the border of any face you alternate house, utility, house, utility… A face’s border is a closed walk, so it uses an even number of pipes, and it cannot be 2 (that would be two pipes joining the same pair). So every face is bordered by at least 4 pipes.
• Add that up over all 5 faces: at least 4 × 5 = 20 pipe-sides. But each pipe has exactly two sides, so the total number of pipe-sides is exactly 2 × 9 = 18. That gives 2E ≥ 4F, i.e. 18 ≥ 20 — which is false.
• A false conclusion from a correct argument means the assumption was wrong: no crossing-free drawing exists. This graph is called K₃,₃, and together with K₅ it is one of the two shapes Kuratowski proved every non-planar drawing must contain (1930).
• The surface is what matters. Euler’s formula on a doughnut reads V − E + F = 0, which gives F = 3, and 2E ≥ 4F becomes 18 ≥ 12 — true, no contradiction. And indeed it can be done there: switch to the doughnut and look.

Controls: drag from a house to a utility to lay a pipe · arrow keys pick a pair, Enter lays it, Backspace removes it · on the doughnut, drag to orbit and scroll or pinch to zoom.