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. |