An upper bound for a graph Ramsey number I am trying to prove the following result, given as an exercise in my book:
$r(K_m+\bar{K_n},K_p+\bar{K_q})\le\binom{m+p-1}{m}n+\binom{m+p-1}{p}q$.
Here $r(G,H)$ denotes the Ramsey number for the graphs $G$ and $H$, i.e. the smallest positive integer $t$, such that any graph $F$ of order $t$ either contains $G$ or $\bar{F}$ (the complement of $F$) contains $H$. The join of graphs $G+H$ is defined as the graph obtained by first drawing $G\cup H$ and then filling out all possible edges between the vertices of $G$ and $H$.
Any help will be appreciated. Thanks.
 A: We want to show that
$$r(K_m+\bar{K_n},K_p+\bar{K_q}) \le \dbinom{m+p-1}{m}n + \dbinom{m+p-1}{p}q.\tag*{(1)}$$
When $n = q = 1$, $(1)$ becomes
$$r(K_{m+1},K_{p+1}) \le \dbinom{m+p-1}{m} + \dbinom{m+p-1}{p} = \dbinom{m+p}{m} \tag*{(2)}.$$
This classical bound follows from the well-known inequality
$$r(K_{m+1},K_{p+1}) \le r(K_{m},K_{p+1}) + r(K_{m+1},K_{p}) \tag*{(3)}.$$
(The inequality $(2)$ follows from $(3)$ by induction on $m + p$.  For the base cases, observe that, e.g., $r(K_{2},K_{p+1}) = p + 1$.)
The fact that the desired inequality is an easy generalization of a classical result gives a strong hint as to the best way to approach the proof.  Happily, $(1)$ does indeed follow along the same lines as the standard proof of $(2)$.
Claim: If $m$, $p \geq 2$ and $n$, $q \geq 0$, then
$$r(K_m+\bar{K_n},K_p+\bar{K_q}) \leq r(K_{m-1}+\bar{K_n},K_p+\bar{K_q}) + r(K_m+\bar{K_n},K_{p-1}+\bar{K_q}).$$
Proof: Set $N = r(K_{m-1}+\bar{K_n},K_p+\bar{K_q}) + r(K_m+\bar{K_n},K_{p-1}+\bar{K_q})$ and two-color $E(K_N)$ arbitrarily with the colors red and blue.  Choose $x \in V(K_N)$.  By choice of $N$, it is easy to see that there must be either $r(K_{m-1}+\bar{K_n},K_p+\bar{K_q})$ red edges incident to $x$ or $r(K_m+\bar{K_n},K_{p-1}+\bar{K_q})$ blue edges incident to $x$.  Without loss of generality, suppose that the latter holds.  Let $U$ denote the set of vertices $u$ such that $ux$ is blue.  Now consider the edges among the vertices of $U$.  If these contain a red copy of $K_m+\bar{K_n}$, then we are done.  If not, then by hypothesis they must contain a blue copy of $K_{p-1}+\bar{K_q}$.  However, all of the edges from $x$ to $U$ are blue, so $x$ and the copy of $K_{p-1}+\bar{K_q}$ form a blue copy of $K_{p}+\bar{K_q}$. $\square$
We are nearly done.  By induction on $m + p$, we have
$$r(K_m+\bar{K_n},K_p+\bar{K_q}) \le \dbinom{m+p-2}{m-1}n + \dbinom{m+p-2}{p}q\\ + \dbinom{m+p-2}{m}n + \dbinom{m+p-2}{p-1}q,$$
and
$$\dbinom{m+p-2}{m-1}n + \dbinom{m+p-2}{p}q + \dbinom{m+p-2}{m}n + \dbinom{m+p-2}{p-1}q = \dbinom{m+p-1}{m}n + \dbinom{m+p-1}{p}q.$$
Finally, for the base case, one can show by the same method as above that $r(K_1+\bar{K_n},K_1+\bar{K_q}) \le n + q$.  This completes the proof.
