6.1 Combinatorial Arguments in Set Theory and Geometry 2914.m= 4 ,n=3, in which caseE=12,V=6,F=8; this is the regular octahedron.5.m= 5 ,n=3, in which caseE =30,V =12,F =20; this is the regular
icosahedron.We have proved the well-known fact that there are five Platonic solids. 848.In the plane are givenn>2 points joined by segments, such that the interiors of any
two segments are disjoint. Find the maximum possible number of such segments
as a function ofn.
849.Three conflicting neighbors have three common wells. Can one draw nine paths
connecting each of the neighbors to each of the wells such that no two paths inter-
sect?
850.Consider a polyhedron with at least five faces such that exactly three edges emerge
from each vertex. Two players play the following game: the players sign their
names alternately on precisely one face that has not been previously signed. The
winner is the player who succeeds in signing the name on three faces that share a
common vertex. Assuming optimal play, prove that the player who starts the game
always wins.
851.Denote byVthe number of vertices of a convex polyhedron, and bythe sum of
the (planar) angles of its faces. Prove that 2πV−= 4 π.
852.(a) Given a connected planar graph whose faces are polygons with at least three sides
(no loops or bigons), prove that there is a vertex that belongs to at most five edges.
(b) Prove that any map in the plane can be colored by five colors such that adjacent
regions have different colors (the regions are assumed to be polygons, two regions
are adjacent if they share at least one side).
853.Consider a convex polyhedron whose faces are triangles and whose edges are ori-
ented. Asingularityis a face whose edges form a cycle, a vertex that belongs only
to incoming edges, or a vertex that belongs only to outgoing edges. Show that the
polyhedron has at least two singularities.
6.1.5 Ramsey Theory
Ramsey theory is a difficult branch of combinatorics, which gathers results that show
that when a sufficiently large set is partitioned into a fixed number of subsets, one of the
subsets has a certain property. Finding sharp bounds on how large the set should be is a
truly challenging question, unanswered in most cases.
The origins of this field lie in Ramsey’s theorem, which states that for every pair of
positive integers(p, q)there is a smallest integerR(p, q), nowadays called the Ramsey