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

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)$$

-
Your three theorems will not be enough so you will need to think some more. You could use them to prove $2r(k,k) \ge r(k+1,k+1)$, but the inequality is pointing in the wrong direction. – Henry Sep 20 '11 at 22:14

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.
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$?