Combinatorics and Probability 739b
w
b
b b
b
b
b b
w
w
w
w w
w
w
Figure 97848.For finding the upper bound we employ Euler’s formula. View the configuration as
a planar graph, and complete as many curved edges as possible, until a triangulation of
the plane is obtained. IfV=nis the number of vertices,Ethe number of edges andF
the number of faces (with the exterior counted among them), thenV−E+F=2, so
E−F =n+2. On the other hand, since every edge belongs to two faces and every
face has three edges, 2E= 3 F. Solving, we obtainE= 3 n−6. Deleting the “alien’’
curved edges, we obtain the inequalityE≤ 3 n−6. That the bound can be reached is
demonstrated in Figure 98.
Figure 98(German Mathematical Olympiad, 1976)849.If this were possible, then the configuration would determine a planar graph with
V=6 vertices (the 3 neighbors and the 3 wells) andE=9 edges (the paths). Each of its
Ffaces would have 4 or more edges because there is no path between wells or between
neighbors. So
F≤
2
4
E=
9
2
.
On the other hand, by Euler’s relation we have