Prove that $r(k,k) + k \leq r(k + 1, k + 1) $

Question

Prove that

$r(k,k) + k \leq r(k + 1, k + 1)$,

where $r(k,l)$ is the minimum number of vertexes in a Graph, where we have a clique with $k$ vertexes or a stable set with $l$ vertexes.

There are three theorems I know in the area. I tried to prove it using all of them, but I can't find a solution.

$$ r(k, l) \leq r(k -1, l) + r(k, l-1) $$ $$ r(k,k) \geq 2^{\frac{k}{2}} $$ $$ r(k,l) = r(l,k) $$

Answer 1

Suppose that $G$ is a graph with at least $r(k+1,k+1) - k$ vertices. Let $G'$ be the disjoint union of $G$ and $K_k$, the complete graph on $k$ vertices. Then $G'$ has at least $r(k+1,k+1)$ vertices, so it has either a $(k+1)$-clique or a stable set of $(k+1)$ vertices. Can you see how to use these to find either a $k$-clique or a stable set of $k$ vertices in $G$?

Answer 2

Complements to Brian's answer. When $G'$ has a $(k+1)$-clique: Since $G'$ is the disjoint union of $G$ and $K_k$, in addition $K_k$ doesn't contain a $(k+1)$-clique, we get $G$ has a $(k+1)$-clique thus $G$ clearly has a $k$-clique. When $G'$ has a stable set of $(k+1)$ vertices: Since $K_k$ has one and only one indepentdent vertice(if there're two, they are connected due to the completeness of $K_k$, a contradiction). Thus $G$ has a stable set of $(k+1)-1=k$ vertices. Thus $G$ has either a $k$-clique or a stable set of $k$ vertices.