How do we know that Ramsey numbers exist? How do I know that for every values of k and l that exist, a Ramsey number of k and l. This would mean that whatever values for k and l you pick, large enough graphs always contain, either a large clique or a large Independent set. Well, we know that for small values of k and l, the Ramsey numbers do exist. For example, if k and l are both at most 3 then yes. Numbers do exist. We will know them. And later, we will prove that R(k,l) is less than or equal to R(k-1) of l plus R of k and l minus 1. Which gives us an upper bound on the Ramsey number for all values of k and l, which means that for every variable of k and for every variable of l, there exists a Ramsey number R(k,l). Which means whatever radius you fix for k and l, large enough graphs will always contain either a clique of size k, or an independent set of size l. Let us now prove this inequality. This is the main theorem in Ramsey's Theorem. So we want to prove that R(k,l) is less than or equal to than R(k-1,l)+R(k,l-1). How do we do this? Consider a graph g on that many vertices. Note that so that it either contains a Clique of size k or an Independent set of size l In order to do so, we fix on vertex v. And let A denote the set of neighbors of v and B denote the remaining vertices. So v is connected to all vertices in A, and is not connected to any vertex in B. 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.