THIS IS NOT THE DUPLICATE OF ABOVE BECAUSE:I require pigeonhole principle argument to my doubt which is not stated in the answer to above question...
I missed my lecture the day the following theorem for ramsey numbers was proved in the class:
If $m,n$ are integers $\gt 2$ then $R(m,n) \leq R(m-1,n)+R(m,n-1)$
Proof:
$R(m,n)=$ smallest possible size of group of persons s.t. among these either $\exists \,m$ persons mutual friends or $\exists \,n$ mutual enemies.
Let $p=R(m-1,n)\,,q=R(m,n-1)$ and $r=p+q$. Consider the group $\{1,2\ldots,r\}$ of $r$ persons.
Let L=$\{$set of persons friends with '$1$'$\}$ and M=$\{$set of persons enemies with '$1$'$\}$
Then $L\cap M=\phi$ .So, we have $|L|+|M|=|L\cup M|=r-1=p+q-1$
We cannot have $|L|\leq p-1$ and $|M|\leq q-1$ .
$\therefore$ either $|L| \geq p$ or $|M|\geq q$.
This the starting paragraph of the proof which I have stated above. and later the proof is divided into two cases ,(1. when $L$ has atleast $p$ elements. 2.when $M$ has atleast $q$ elements),which I understood...
But what I can't understand is the step at begining of proof that:
We cannot have $|L|\leq p-1$ and $|M|\leq q-1$ .
$\therefore$ either $|L| \geq p$ or $|M|\geq q$.
The above statement makes the use of pigeonhole principle but I don't know how.Please anyone who can help me with this ,as I have no idea for this.....