Can Three Houses Reach Three Wells Without Paths Crossing?: Math Further 6–8

On a hillside village, three families live in three houses in a row, and below them are three wells. Each well is good for something different: one has the sweetest water for drinking, one never runs dry in the months before the monsoon, and one is the nearest when you are in a hurry. So every family wants a path of its own to every well.

But the families don’t get on. Nobody wants to meet a neighbor where two paths cross, so they agree on one rule: no path may cross another. That makes nine paths, from each of the three houses to each of the three wells. The paths may bend and wind as much as you like, and go round the houses and wells, but they may not cross, and they may not run through another house or well on the way.

Can it be done? Try it.

Press on a house and draw a path to a well with your finger or the mouse. If a path crosses another, it stops and shows you where. Take back a path to try it another way round.

Paths drawn: 0 of 9
Most so far: 0 of 9

Press on a house and draw a path to a well.

Draw a few paths, then guess.

Pick an answer to see why.

Smaller villages

When a puzzle is too hard, try a smaller one. Here are villages with only two houses.

Choose a village with the buttons under the picture: two houses and two, three or four wells. Draw every path.

Paths drawn: 0 of 4
Most so far: 0 of 4

Press on a house and draw a path to a well.

a.Can you join two houses to two wells? To three? To four?
b.With two houses, does it matter how many wells there are?
c.Now go back to three houses and three wells at the top of the page. How many paths can you draw, at most?

Trying more and more drawings can’t prove that nine is impossible: there are endless ways to wind a path. To prove it, we need something that is true of every drawing. That something is a count.

Dots, lines and regions

As with Königsberg’s bridges, only one thing matters here: what is joined to what. The size of the houses, the length and shape of the paths: none of it changes which paths can be drawn. So shrink each house and each well to a dot, and each path to a line. A drawing of dots joined by lines is a network, or graph; the dots are its vertices and the lines its edges.

A network that can be drawn on a flat sheet with no lines crossing is called planar (from plane, a flat surface). The village’s question is: is the network of three houses and three wells planar?

When a planar network is drawn, its lines cut the paper into pieces. Each piece is a region, or face; the paper outside the whole drawing counts as one region too. This is the same word you met for solids in Grade 7, when you counted the faces, edges and vertices of a cube. The connection is no accident, as you will see.

Draw some networks and count.

Tap a dot to pick it. Then tap another dot to join them with a straight line, or tap an empty place to put a new dot there, joined to the one you picked. Lines may not cross. The regions are shaded and numbered; the outside’s number is in the corner.

Dots: 4
Lines: 5
Regions: 3
Dots − lines + regions: 4 − 5 + 3 = 2

Tap a dot to start a line from it.

The widget starts with a square and one diagonal. What is dots − lines + regions for it?

Pick an answer to see why.

However you draw, as long as nothing crosses and the network stays in one piece, the last number is always 2:

dots − lines + regions = 2, or V − E + F = 2, with V for vertices, E for edges and F for faces.

This is Euler’s formula, after Leonhard Euler, who also solved the bridges of Königsberg. He found it for solids in 1750: a cube has 8 corners, 12 edges and 6 faces, and 8 − 12 + 6 = 2.

Why it is always 2

The topic Why Do Solids Always Obey One Rule? proves it for every flat drawing. In short: start with one dot on the paper (1 − 0 + 1 = 2) and draw the network one line at a time, each line starting from a dot already drawn. A line out to a new dot adds one dot and one line. A line between two dots already drawn closes a loop and cuts a region in two, so it adds one line and one region. Neither step changes the total, so it stays 2.

Two things in that proof matter for the village. The paper outside the drawing is counted as a region, and the network must be in one piece: two separate triangles, for example, have 6 dots, 6 lines and 3 regions (two insides and one outside), and 6 − 6 + 3 = 3. The village is in one piece, since every house has a path to every well.

A network is drawn with no crossings, all in one piece, with 6 dots and 9 lines. How many regions does it make?

Pick an answer to see why.

Why the ninth path can never be drawn

Suppose someone did draw all nine paths without a crossing. Then the village would be a planar network in one piece with 6 dots and 9 lines, so by Euler’s formula it would cut the paper into exactly 5 regions. Now count in another way.

How many paths round a region? Walk round the edge of any region. The paths always run from a house to a well, so on the way round you meet house, well, house, well… and you come back to where you started. So the number of paths round a region is even. It can’t be 2: a walk round just two paths goes from a house to a well and straight back, either by a second path between the same two, and each house has only one path to each well, or back along the same path, which happens only at a dead end, and every house and well has three paths. So every region has at least 4 paths round its edge.

Count the path-sides. Every path has two sides, and each side faces one region. So if you add up, for every region, the number of paths round it, you count each path twice (a path with the same region on both sides counts twice for that region): the total is 2 × 9 = 18.

But 5 regions, each with at least 4 paths round it, need at least 5 × 4 = 20. A total can’t be 18 and at least 20 at once. So the drawing we supposed can’t exist: the nine paths can never be drawn without a crossing. The network of three houses and three wells is not planar.

Look at the best you can do, eight paths, to see how tight it is.

Figure 25.1 Eight of the nine paths, with houses and wells placed in turn round a ring. They make 4 regions (the fourth is everything outside), each with exactly 4 paths round it. The ninth path, from house 2 to well 3, would have to cross: house 2 touches only regions 1 and 3, well 3 only regions 2 and 4.

With eight paths, Euler’s formula gives 2 − 6 + 8 = 4 regions, and 4 regions × 4 paths = 16 = 2 × 8: the count fits exactly, with nothing to spare. A ninth path would have to start in a region house 2 touches and end in one well 3 touches, and in Figure 25.1 they touch no region in common, so the path would have to cross a line to get from one to the other.

Five temples

Here is the same kind of puzzle with a new rule. Five temples stand on a hill, and the priests want a path from every temple to every other, with no paths crossing. That is 10 paths (each of the 5 temples has 4, and each path is counted at both ends: 5 × 4 ÷ 2 = 10).

Try to join every temple to every other. (Leave “With one bridge” for later in the topic.)

Paths drawn: 0 of 10
Most so far: 0 of 10

Press on a temple and draw a path to another.

You can draw 9 of the 10. Can you prove that the tenth is impossible, the way we did for the wells?

These two networks are famous. In the language of graphs, three houses joined to three wells is called $K_{3,3}$ , and five dots each joined to every other is K₅. In 1930 the Polish mathematician Kazimierz Kuratowski proved something astonishing about them: they are the only two obstacles. A network can be drawn flat without crossings unless a copy of one of these two is hidden inside it, perhaps with extra dots along its lines. Every network that can’t be drawn flat has three houses and three wells, or five temples, buried somewhere in it.

Ways round the rule

When a rule makes a puzzle impossible, it’s worth asking exactly which part of the rule does it. Change one part and the puzzle can come back to life.

A path through a house

In his book of 1917 the English puzzle writer Henry Dudeney printed the puzzle as “Water, Gas, and Electricity”: lay pipes from the water, gas and electricity works to three houses without any pipe crossing another. His answer admitted that, taken strictly, there is no solution, and then cheated: if one householder lets a pipe for another house run through his property, the pipes never cross. In our village, that is a path that goes in at one house’s front door and out at the back. Our widget doesn’t allow it, and the proof above doesn’t either, since a path through a house would meet the house’s other paths there.

One bridge

What if the families build one little footbridge, so that one path may cross over another just once?

Choose “With one bridge” in the widget of the five temples above. It is the village again, but the first time a path crosses another, a bridge is built there and the path carries on. A second crossing is still not allowed.

On a doughnut

Euler’s formula was about a flat sheet of paper. On a different surface the count changes, and so does the answer.

Figure 25.2 All nine paths with no crossings, on a doughnut. The square is a sheet whose top edge is joined to its bottom edge, and its left edge to its right edge, as the arrows show: a path that runs off the top comes back on at the same place on the bottom. Roll the sheet into a tube, then bend the tube round until its ends meet, and it becomes the surface of a doughnut.

On the surface of a doughnut, or a cup with a handle, the three houses and three wells can all be joined. The paths that leave the square in Figure 25.2 go round the doughnut’s ring or through its hole. Count the regions there: the nine paths cut the doughnut into just 3, and 6 − 9 + 3 = 0. On a doughnut, Euler’s sum comes out as 0 instead of 2, and the count that blocked the ninth path no longer does: 3 regions with at least 4 paths round each need only 3 × 4 = 12 path-sides, and the nine paths have 18.

A story from maths

Dudeney, Kuratowski and a brick factory

Nobody knows who first asked the puzzle. Henry Ernest Dudeney (1857–1930), England’s great puzzle writer, printed it in The Strand Magazine in 1913 and in his book Amusements in Mathematics in 1917, where he called it “as old as the hills”, and much older than electric lighting or even gas. Versions with three houses and three wells appeared in American magazines in 1914 and 1916. The American puzzle maker Sam Loyd is said by his son to have published it in 1900, but no copy has been found.

Puzzle writers such as Dudeney already said there was no solution. In 1930 Kazimierz Kuratowski (1896–1980) of Warsaw published his theorem that $K_{3,3}$ and K₅ are the only obstacles to drawing a network flat. He stated that $K_{3,3}$ can’t be drawn flat, so the village can’t be done, but, as David Kullman pointed out in a history of the puzzle in 1979, he didn’t publish a detailed proof of that part. The counting proof in this topic needs only Euler’s formula. In the Soviet Union his theorem was called the Pontryagin–Kuratowski theorem: Lev Pontryagin is said to have proved it around 1927, but he never published his proof. During the Second World War, when the German occupation forbade higher education for Poles, Kuratowski taught at Warsaw’s secret underground university.

The puzzle’s next chapter began in a labor camp. In July 1944 the Hungarian mathematician Pál Turán (1910–1976), forced into labor service because he was Jewish, was pushing wagons of bricks at a brick factory near Budapest. Rails ran from every kiln to every storage yard, and where two rails crossed, the wagons jolted and bricks fell out. Turán began to wonder how few crossings the rails could have, for any number of kilns and yards. Three kilns and three yards is our village again, and the answer is 1. For bigger factories the question, called Turán’s brick factory problem, is still not fully solved (as of 2026).

An old black-and-white portrait of a man with a white beard and moustache, resting his head on his hand — **Figure 25.3** Henry Ernest Dudeney, about 1910. Photo: Unknown author, Public domain

Where this is used

Computer programs can test any network for planarity quickly: in 1974 John Hopcroft and Robert Tarjan published the first method whose time grows only in proportion to the size of the network, so a network ten times bigger takes only about ten times as long to check.

Questions

★ Which of these villages can be drawn with no paths crossing?

Pick an answer to see why.

Figure 25.4 A cube’s corners and edges drawn flat: you are looking into an open box from above, so the bottom of the box is the small square.

a.★

In Figure 25.4, count the dots, the lines and the regions (remember the outside). Check Euler’s formula. Which region is the cube’s top face, the face that was missing from the open box?

Answer

★★ A network is drawn without crossings, all in one piece, with 10 dots and 15 lines. How many regions are there, counting the outside?

Pick an answer to see why.

b.★★

A network in one piece has 7 dots and 12 lines, and none of its regions could ever be a triangle (every loop in it has at least 4 lines). Show that it can’t be drawn without crossings. Then use the same idea on 3 houses and 4 wells.

Hint

Answer

c.★★

Dudeney’s trick let one path pass through a house. In our village, which path could you send through house 1 to solve the puzzle, if the eight paths are drawn as in Figure 25.1?

Hint

Answer

d.★★★

Show that a network drawn without crossings, in one piece, with at least 3 dots and no two lines joining the same pair of dots, can have at most 3 × (dots) − 6 lines. Use it to show again that the five temples can’t be joined.

Hint

Answer

Quiz yourself on this unit →

Where to go next

Why Do Solids Always Obey One Rule? Euler’s formula for solids: why every solid’s corners − edges + faces is 2, and the solids where it isn’t.
Can You Cross Every Bridge Just Once? Euler’s first network puzzle: a walk over every line exactly once.
What Is the Quickest Way Across the Map? Networks with a time on every road, and how to find the fastest route.
Can Four Colors Paint Any Map of Nepal? (Computing, Going Further 6–8) A map is a planar network of neighbors, and four colors are always enough.
How Do You Connect Every Village with the Least Cable? (Math, Going Further 9–12) Networks again, now the cheapest way to join every place.

Where these facts come from

The puzzle’s history (Dudeney in The Strand Magazine, 1913, and Amusements in Mathematics, 1917; the three-wells versions of 1914 and 1916; Sam Loyd’s son’s claim of 1900), Kuratowski’s statement of 1930 that $K_{3,3}$ can’t be drawn flat and Kullman’s remark (1979, as quoted there) that he published no detailed proof, the proof by Euler’s formula with at least four edges a face, the doughnut (torus) solution, crossing number 1: Wikipedia, “Three utilities problem”, read October 2026.
Dudeney’s puzzle 251, “Water, Gas, and Electricity”, its words (“as old as the hills”, “much older than electric lighting, or even gas”) and his answer through house A, retold in our words: H. E. Dudeney, Amusements in Mathematics (1917, public domain), Project Gutenberg, read October 2026.
Kuratowski’s theorem (K₅ and $K_{3,3}$ the only obstacles, 1930; Frink and Smith; Pontryagin about 1927, unpublished): Wikipedia, “Kuratowski’s theorem”; his dates and the underground university: Wikipedia, “Kazimierz Kuratowski”, read October 2026.
Euler’s formula for planar networks, at most 3V − 6 edges, at most 2V − 4 with no triangles, two-sided circuit boards: Wikipedia, “Planar graph”, read October 2026. Euler’s formula for solids found by Euler in 1750 (his letter to Goldbach; the paper printed in 1758), as sourced in Why Do Solids Always Obey One Rule?; the torus’s value 0: Wikipedia, “Euler characteristic”, read October 2026.
Turán’s brick factory (July 1944, near Budapest, rails from kilns to storage yards, bricks falling at crossings), his labor service and dates, and the problem still open: Wikipedia, “Turán’s brick factory problem” and “Pál Turán”, read October 2026.
Circuit boards: wires can cross only on different layers, joined by vias, and the houses and utilities puzzle as the start of routing: Behrooz Parhami, “Placement and Routing”, University of California, Santa Barbara, 2007; vias: Wikipedia, “Via (electronics)”, read October 2026.
Hopcroft and Tarjan’s planarity test, the first in linear time, 1974: Wikipedia, “Planarity testing”, read October 2026.
Dudeney’s portrait: Wikimedia Commons, public domain.
Every number in the topic (which villages can be drawn, 8 of 9 and 9 of 10 as the best, the regions in each example, the counts 18 against 20 and 20 against 21, the two triangles’ 3, the cube’s 8, 12 and 6, the doughnut drawing and its 3 regions, the bounds 3V − 6 and 2V − 4) was computed by programs of our own.