# Huts and wells

Let's recall two puzzles as old as the world itself. The first is about three huts and three wells and the problem consists in tracing paths connecting each hut with each well, with one condition capriciously imposed by the hut owners: no two different paths can meet.

There are no wells in the second puzzle, though there are five huts instead. Now the puzzle-solver is asked to design paths connecting the huts so that any two of the latter have a direct connection, i.e., one that does not require visiting other huts on the way. As before, no two different paths are allowed to meet.

Almost everyone who first hears any one of these two puzzles grabs a pencil and a sheet of paper, only to state after a few attempts that this cannot be done. Indeed, at first everything goes smoothly; by the end, however, it always turns out that there is no way of placing the last missing path without crossing the previous ones. If you have never lived this experience before, try for yourself now.

In fact, both in mathematics and beyond it a series of failures is no proof of something being impossible. We will therefore rigorously justify the fact that no solutions exist for the two puzzles and here is where Euler's formula comes in.

Suppose we have a graph on the plane, i.e. a number of dots connected by non-crossing lines. Assume moreover that each dot can be reached from any other through a sequence of lines (which intuitively means that the graph is made of one piece and not of two, three or more parts lying at some distance from each other). In this case we say the graph is connected. Euler's formula states that in a connected graph the number V of dots, the number E of lines and the number F of parts which the graph cuts the plane into are related by the equation V-E+F=2. Some examples are shown in Fig. 1 below and those of you who prefer to avoid looking for the not too complicated proof of this equation may verify the statement experimentally on some other connected graphs of their choice.

Fig. 1. In the graph above (the hut) F=4, V=12, E=14; for the lower graph (the plane) the values are F=6, V=23, E=27.

In the first problem we have V=3+3=6, E==9 (for each hut must be connected with each well). Thus Euler's formula implies that F must be 5. If we could draw a solution to the puzzle, each of the five parts of the plane should be bounded by at least four lines. Indeed, two or three would not be sufficient, since in the first case we would have two different lines going from one hut to the same well, in the second - two wells or two huts connected by a direct path, which is not allowed. But then there must be at least lines (we must divide by 2, because each line bounds two parts of the plane) and this is too many! The contradiction proves that there is no solution to the problem of huts and wells.

In the second problem we have V=5 and E= (because each hut must be connected with each of the four remaining ones and no line should be counted twice). Therefore F should be equal to 2+E-V=7. If we could draw such a graph, each of the seven parts would now have a border consisting of three lines, as implied by the requirement that each hut be connected with each other. Recounting our lines as before, we get E= - a contradiction again.

You might say: instead of repeating old and well-known puzzles, why don't you offer us a new one, so that we can make a brilliant show at our parents' party or at our math class (delete what does not apply), It turns out that there can be no really new puzzle on drawing plane graphs - and this is not because of our laziness, which we try not to exhibit, but to a theorem proved by Kazimierz Kuratowski in 1930: any graph which cannot be drawn on the plane without crossing lines contains one of the two elements shown in Fig. 2, where you will easily discover the huts and the wells.

Fig. 2. For the hexahedron with the diagonal, V=5, E=10, while for the tetrahedron with an added axis of symmetry, V=6, E=9.

Pawel Strzelecki