Combinatorics and Probability 745then−1 edges starting atx. Among them there are eitherR(p− 1 ,q)red edges, or
R(p, q− 1 )blue edges. Without loss of generality, we may assume that the first case is
true, and letXbe the set of vertices connected toxby red edges. The complete graph
onXhasR(p− 1 ,q)vertices. It either has a blue complete subgraph withqedges, in
which case we are done, or it has a red complete subgraph withp−1 edges, to which
we add the red edges joiningxtoXto obtain a red complete subgraph withpedges of
the original graph. This provesR(p, q)≤R(p− 1 ,q)+R(p, q− 1 ).
To prove the upper bound for the Ramsey numbers we argue by induction onp+q.
The base case consists of all configurations withp=2orq=2, in which caseR(p, 2 )=
R( 2 ,p)=p=
(p
p− 1)
, since any graph withpvertices either has an edge colored red,
or is entirely colored blue. Let us assume that the inequality is true for allp, q≥2,
p+q=n. Eitherp=2, orq=2, or otherwise
R(p, q)≤R(p− 1 ,q)+R(p, q− 1 )≤(
p+q− 3
p− 2)
+
(
p+q− 3
p− 1)
=
(
p+q− 2
p− 1)
.
(P. Erdos, G. Szekeres) ̋856.We prove the property by induction onk. First, observe that
k!e=k!
1+
k!
1!+
k!
2!+···+
k!
k!.
Fork=2,k!e+ 1 =6, and the property was proved in the previous problem. Assume
that the property is true for a complete graph replaced with(k− 1 )!e+1 vertices
colored byk−1 colors, and let us prove it for a complete graph withk!e+1 vertices
colored bykcolors. Choose a vertexvof the graph. By the pigeonhole principle,vis
connected to(k!e+ 1 )/k+1 vertices by edges of the same colorc. Note that
⌊
k!e+ 1
k
⌋
+ 1 =
⌊
1
k(
k!
1+
k!
1!+
k!
2!+···+
k!
k!)⌋
+ 1
=
(k− 1 )!
1+
(k− 1 )!
1!+
(k− 1 )!
2!+···+
(k− 1 )!
(k− 1 )!+ 1
=(k− 1 )!e+ 1.If two of these vertices are connected by an edge of colorc, then ac-colored triangle
is formed. If not, the complete graph on these(k− 1 )!e+1 vertices is colored by
the remainingk−1 colors, and by the induction hypothesis a monochromatic triangle is
formed. This completes the proof.
Remark.This proves that thek-color Ramsey numberR( 3 , 3 ,..., 3 )is bounded from
above byk!e+1.
(F.P. Ramsey)