Now whenever the total number of vertices in this graph is a size of A plus
the size of B plus 1, we're going to count the vertex v itself.
On the other hand, the number of vertices in this
graph is R(k- 1,l) + R(k, l- 1).
From this, we can conclude that either A is greater than
R of k minus 1 and or B is greater than R of k and l minus one.
Indeed, assume what?
Assume both of them are less than their sum plus one will
be smaller than R o (k-1) and l plus R(kl-1).
So just one of these inequalities must hold.
Let us now assume that the first inequality holds,
namely that A is greater than or equal to R(k- 1,l).
By the definition of this Ramsey number, it means that either
the subgraph on on A vertices contains an independent set of size l.
In which case, we are done because it means that our original graph contains
an independent set of size l.
That's exactly what we want to prove.
Or maybe this graph on A only contains a clique of size k- 1.
But this case is also good for us, because now we can add v to these vertices from A.
And since v is connected to all vertices from A,
they all together form a clique of size k.
Which is, again, exactly what we want to prove.
So in one case, we show that there exists a large independent set.
In the other case we show that there exists a large clique.
This was the first case.
The second case is when B is greater than or equal to a power k(l-1).
And again, the definition of the Ramsey number,
this means that either B has a k-clique, which is good for us, we're done.
Our original class is k-clique.
Or maybe B contains an independent set of size only l-1.
But now, again, we join the set b with our vertex v.
Since v is not connected to anything in B, it altogether form
an independent set of size l, exactly what we wanted to find.
Now, let's see how this proof works on an example.
Let me draw all the labels of the vertex B, on the left, and
all the vertices which are not connected to B, on the right.
So the left, I have this part of the graph we check called A in the proof, and
on the right, I have this part of the graph which I call B in the proof.
In those two cases, I assert A is greater than R(k -1, l) or
B is greater than R of k l minus 1.
Consider the first case.
But the definition of this Ramsey number (k-1,l)
either A contains an independent set of size l.
Which means our graph contains an independent set of size l and better.
Or A contains a Clique of size k-1.
But then, we're going to add this word XV to the clique, and
we'll have a clique of size K which is good.
This is exactly what we wanted to find.
If that's the case, if B is large,
then again I said B contains a K clique, which is good for us.
Or B contains an independent set of size L-1.
And then we can add there, third [INAUDIBLE] theory, and
get an independent set of size L.