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

Question

Demostrar que

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

donde $r(k,l)$ es el mínimo número de vértices en una Gráfica, donde tenemos una camarilla con $k$ vértices o un conjunto estable con $l$ vértices.

Hay tres teoremas que conozco en la zona. Traté de demostrarlo con todos ellos, pero no puedo encontrar una solución.

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

Complementa a la de Brian respuesta. Al $G'$ $(k+1)$- clique: Desde $G'$ es distinto de la unión de $G$$K_k$, además de la $K_k$ no contiene un $(k+1)$-clique, obtenemos $G$ $(k+1)$- la camarilla de lo $G$ tiene claramente un $k$-clique. Al $G'$ tiene un conjunto estable de $(k+1)$ vértices: Desde $K_k$ tiene uno y sólo uno indepentdent vértice(si no son dos, están conectados debido a la integridad de $K_k$, una contradicción). Por lo tanto $G$ tiene un conjunto estable de $(k+1)-1=k$ vértices. Por lo tanto $G$ ha $k$-camarilla o un conjunto estable de $k$ vértices.

Answer 2

Supongamos que $G$ es un gráfico con al menos $r(k+1,k+1) - k$ vértices. Deje $G'$ ser distinto de la unión de $G$$K_k$, el grafo completo en $k$ vértices. A continuación, $G'$ tiene al menos $r(k+1,k+1)$ vértices, por lo que tiene un $(k+1)$-camarilla o un conjunto estable de $(k+1)$ vértices. Se puede ver cómo utilizar estas para encontrar un $k$-camarilla o un conjunto estable de $k$ vértices en $G$?