Problema 12
A una fiesta asistieron 10 personas. Se sabe que entre cualesquiera tres de ellas, hay al
menos dos que no se conocen. Muestra que en la fiesta hay un grupo de cuatro personas que no se conocen entre si.
Solucion:
Representemos a cada persona i con un vertice $v_i$ y uniremos dos vertices con aristas
rojas o verdes dependiendo si las dos personas correspondientes se conocen o no. Si $v_1$ tiene
al menos 6 aristas verdes de las 9 aristas que salen de $v_1$, tomamos los vertices que estan unidos a $v_1$ por estas aristas verdes, digamos $v_2$, $v_3$, $\dots$, $v_7$. Ahora si
$v_2$ tiene al menos $3$ aristas verdes de las 5 aristas que lo unen con $v_3$, $\dots$, $v_7$, entonces tomamos esos vertices, digamos $v_3$, $v_4$, $v_5$. Entre estos tres vertices hay al menos dos unidos por una arista verde digamos $v_3$ y $v_4$. Entonces $v_1$, $v_2$, $v_3$,
$v_4$ estan unidos unicamente por aristas verdes y terminamos.
Si $v_2$ no tiene al menos 3 aristas verdes, entonces tiene al menos 3 aristas rojas. Tomamos los 3 vertices de esas aristas rojas, digamos que son $v_3$, $v_4$, $v_5$. Entonces entre estos 3 vertices no hay 2 que esten unidos por una arista roja. Luego, $v_1$, $v_3$, $v_4$, $v_5$ estan unidos unicamente por aristas verdes y terminamos.
Finalmente si $v_1$ no tiene al menos 6 aristas verdes, tiene al menos 4 aristas rojas y tomando los vertices de esas aristas rojas, digamos, $v_2$, $v_3$, $v_4$, $v_5$, entonces entre estos vertices no hay 2 que este unidos por una arista roja y por lo tanto, estan unidos unicamente por aristas verdes y nuevamente terminamos.