Principio de las casillas en aristas desde un vértice.
El número de Ramsey $R(r, s)$ es el entero más pequeño $n$ tal que cualquier coloración de las aristas del grafo completo $K_n$ con dos colores (normalmente Rojo y Azul) contiene ya sea un subgrafo completo Rojo de tamaño $r$ ($K_r$) o un subgrafo completo Azul de tamaño $s$ ($K_s$). El caso específico $R(3,3) = 6$ es el resultado introductorio más famoso en la Teoría de Ramsey, y seguro lo conoces como el "Teorema de los Amigos y Extraños". Dice que en cualquier grupo de seis personas, siempre vas a encontrar a tres que son amigos entre sí o a tres que son completos desconocidos.
Este resultado es clave porque sirve como el caso base para demostrar que los números de Ramsey siempre existen. La técnica de la demostración muestra el camino estándar para poner cotas superiores en los números de Ramsey: eliges un vértice cualquiera y aplicas el Principio de las Casillas a las aristas que salen de él. Esto reduce el problema en $K_n$ a un subproblema en un grafo más chico, aprovechando que la Teoría de Ramsey es recursiva.
Para demostrar que $R(3,3) = 6$, tienes que probar dos desigualdades: $R(3,3) > 5$ (la cota inferior) y $R(3,3) \