El ejercicio describe un grafo simple no dirigido $G$ en $251$ vértices que es regular de grado $168$ . Es decir, cada vértice (alumno) tiene $168$ bordes (conexiones con otros estudiantes con los que pueden trabajar). ¿Tiene $G$ contienen un $4$ -clique, $K_4$ ?
Esta situación se resuelve inmediatamente Thm. de Turán lo que da un límite superior al número de aristas que un $n$ -El gráfico de vértices puede tener y seguir teniendo $K_{r+1}$ -gratis.
Ese límite superior es:
$$ \left\lfloor \left( 1 - \frac{1}{r} \right) \cdot \frac{n^2}{2} \right\rfloor $$
Para el caso inmediato tomamos $n=251$ y $r=3$ (ya que se trata de evitar $(r+1)$ -cliques), y obtenemos como máximo $21000$ bordes.
Pero contando los bordes en $G$ encontramos que tiene $251\cdot 168/2 = 21084$ bordes. Así que $G$ no está libre de $4$ -cliques.
Con un poco más de esfuerzo podemos demostrar que los datos de este ejercicio implican una conclusión más sólida:
Cada vértice de $G$ pertenece al menos a una $4$ -clique.
Para verlo, fija cualquier vértice $u\in G$ y considerar la vecindad eliminada $H$ de $u$ El $168$ otros vértices de $G$ junto a $u$ . Desde $G\setminus \{u\}$ tiene $250$ vértices, hay $250-168=82$ vértices en $G$ pero no en $H\cup \{u\}$ .
Puesto que cada $v\in H$ tiene $167$ vecinos en $G\setminus \{u\}$ como $v$ debe tener al menos $167-82 = 85$ vecinos en $H$ . Ahora aplicamos el caso especial del Thm. de Turán cuando $r=2$ a saber Mantel's Thm. que dice:
El número máximo de aristas en un $n$ -El grafo triangular sin vértices es $\lfloor n^2/4 \rfloor$ .
Poner $n=168$ da un límite superior de $168^2/4 = 7056$ bordes si $H$ no tiene triángulos. Pero como cada $v\in H$ tiene (al menos) $85$ vecinos allí, $H$ debe tener al menos $85\cdot 168/2 = 7140$ bordes.
De ello se deduce que $H$ contiene un triángulo, y junto con el primer vértice $u$ forma un $4$ -clique en $G$ .
Los lectores con un mínimo interés en la demostración de Thm. (1941) de Turán les recomendamos que consulten la exposición de Martin Aigner, Teorema del grafo de Turán (1995) . Allí se examinan media docena de pruebas, empezando por un tratamiento de media página del caso especial utilizado más arriba, el Thm. de Mantel. (1906).
0 votos
Su pregunta final, "¿es [2] el número mínimo de alumnos que eligen a alguien que no les ha elegido a ellos?", no concuerda con el ejercicio citado: "Para dos alumnos cualesquiera de la clase, si el alumno A pone al alumno B en su lista, entonces el alumno B también tendrá al alumno A en su lista". Así que creo que no has entendido el sentido del ejercicio.