6.1 Combinatorial Arguments in Set Theory and Geometry 289845.Inside a square of side 38 lie 100 convex polygons, each with an area at mostπ
and the perimeter at most 2π. Prove that there exists a circle of radius 1 inside the
square that does not intersect any of the polygons.
846.Given a setMofn≥3 points in the plane such that any three points inMcan be
covered by a disk of radius 1, prove that the entire setMcan be covered by a disk
of radius 1.
847.Prove that if a convex polyhedron has the property that every vertex belongs to an
even number of edges, then any section determined by a plane that does not pass
through a vertex is a polygon with an even number of sides.
6.1.4 Euler’s Formula for Planar Graphs
This section is about a graph-theoretical result with geometric flavor, the famous Euler’s
formula. Recall that a graph is a collection of points, called vertices, some of which are
joined by arcs, called edges. A planar graph is a graph embedded in the plane in such a
way that edges do not cross. The connected components of the complement of a planar
graph are called faces. For example, the graph in Figure 39 has four faces (this includes
the infinite face). Unless otherwise specified, all our graphs are assumed to be connected.
Figure 39Euler’s theorem.Given a connected planar graph, denote byVthe number of vertices,
byEthe number of edges, and byFthe number of faces(including the infinite face).
Then
V−E+F= 2.Proof.The proof is an easy induction onF.IfF=1 the graph is a tree, and the number
of vertices exceeds that of edges by 1. The formula is thus verified in this case.
Let us now consider someF>1 and assume that the formula holds for all graphs
with at mostF−1 faces. Since there are at least two faces, the graph is not a tree.
Therefore, it must contain cycles. Remove one edge from a cycle. The new graph is still