Hace 3-partita gráfico con al menos n+1 aristas por vértice tiene un triángulo?

Question

Necesito ayuda para un problema.

En cada una de las 3 escuelas que hay n los estudiantes (en total = 3n de vértices, n por la escuela). Cada estudiante sabe al menos n+1 a los estudiantes de las otras dos escuelas. Demostrar que hay 3 estudiantes, uno de cada escuela, los que conocen a cada otros.

¿Tiene usted alguna idea para esta prueba?

Answer 1

Deje $G$ ser un contraejemplo, es decir, un 3-partita gráfico con $n$ vértices en cada partita conjunto y su grado mínimo $n+1$ que no tiene ningún triángulo.

Deje $v$ ser un vértice que maximiza el número de vecinos que tiene en una partita conjunto, decir $k$. Podemos etiqueta de la partita conjuntos de $A,B,C$, de tal manera que $v\in A$ $v$ $k$ vecinos en $B$. Desde $k\leq n$, $v$ tiene al menos un vecino en $C$, decir $w$.

$w$ tiene más de $n-k$ vecinos en $B$ (de lo contrario nos encontramos con un triángulo que implican $v,w$ y un vértice de $B$), por lo $w$ tiene al menos $(n+1)-(n-k)=k+1$ vecinos en $A$. Esto contradice la elección de $v$.

Hecho.

(Este problema se despertó mi interés en la nitidez de la pregunta: ¿es cierto que para un determinado$n$, e incluso el $k<3n(n+1)$ siempre hay un 3-partita gráfico con $n$ vértices en cada partita conjunto y total grado en la mayoría de las $k$ (y su grado mínimo, al menos,$n$?) que no tiene ningún triángulo?)