Three Houses, Three Utilities

  • Medium
  • Geometry and grid puzzles
  • Tests: Knowing when a drawing cannot be flattened

The puzzle

Three houses each need connecting to three utilities - gas, water and electricity - by nine lines drawn on a flat sheet, with no line crossing another and no line passing through a house or a utility.

Can it be done? If not, show why not.

Stuck?

One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.

Hint 1

Count the lines and the points first: 6 points and 9 lines.

Hint 2

Euler's formula for a flat drawing without crossings is V − E + F = 2. Work out what F would have to be.

Show the answer Hide the answer

It cannot be done on a flat sheet. Euler's formula gives a face count the drawing cannot support.

How to get there

Suppose it could be drawn flat with no crossings. There are V = 6 points and E = 9 lines, so Euler's formula V − E + F = 2 forces F = 5 faces.

Now count edges round the faces. Every line joins a house to a utility, so any closed loop alternates house, utility, house, utility - and must therefore have at least 4 edges. Each edge borders two faces, so 2E is at least 4F, giving 18 ≥ 20. False.

The contradiction kills the assumption: no flat drawing exists. It is perfectly possible on a doughnut, where the extra handle lets one line go round the back - which is why the puzzle has to specify a flat sheet. This graph is called K3,3 and, with K5, it is one of the two obstructions that make any graph unflattenable.

The technique worth keeping

Euler's formula turns "can this be drawn without crossings" into arithmetic. Derive the face count it forces, then bound the edges round each face using the structure - a contradiction there is a proof of impossibility.