744 Combinatorics and Probability
Remark.The polyhedron can be thought of as a discrete approximation of a surface. The
orientation of edges is the discrete analogue of a smooth vector field on the surface. The
numbern 1 +n 2 +n 3 +n 4 is called the total index of the vector field. The result we just
proved shows that if the polyhedron resembles a (triangulated) sphere, the total index of
any vector field is 2. This is a particular case of the Poincaré–Hopf index theorem, which
in its general setting states that given a smooth vector field with finitely many zeros on
a compact, orientable manifold, the total index of the vector field is equal to the Euler
characteristic of the manifold.
854.Figure 103 shows that this number is greater than or equal to 5.
Figure 103Let us show that any coloring by two colors of the edges of a complete graph with 6
vertices has a monochromatic triangle. Assume the contrary. By the pigeonhole principle,
3 of the 5 edges starting at some point have the same color (see Figure 104). Each pair
of such edges forms a triangle with another edge. By hypothesis, this third edge must be
of the other color. The three pairs produce three other edges that are of the same color
and form a triangle. This contradicts our assumption. Hence any coloring of a complete
graph with six vertices contains a monochromatic triangle. We conclude thatn=5.
Figure 104Remark.This shows that the Ramsey numberR( 3 , 3 )is equal to 6.
855.Letn=R(p− 1 ,q)+R(p, q− 1 ). We will prove that for any coloring of the
edges of a complete graph withnvertices by red or blue, there is a red complete subgraph
withpvertices or a blue complete subgraph withqvertices. Fix a vertexxand consider