Gráfico tripartito n 1-regular que contiene un triángulo

Question

Suponga un gráfico tripartito,$(n+1)$ - regular. Cada uno de sus$3$ parts$(A,B,C)$ contiene$n$ nodos. Demuestre que el gráfico contiene un triángulo.

Creo que el hecho de que es$n+1$ y no$n$ juega un papel importante porque habrá por lo menos una ventaja en ambos$B,C$, dejar que el borde `comience 'desde$A$.
También traté de usar el principio de casillero pero me falta algo. ¿Algunas ideas?

Answer 1

Suponga $G$ no contiene un triángulo.

Deje $A,B,C$ los tres partita conjuntos. Deje $v$ ser un vértice que maximiza el número de vecinos que tiene en uno de los otros partita conjuntos (así que no hay vértice tener más vecinos en una sola partita conjunto de $v$).

Por simetría podemos suponer que la $v\in A$, $v$ $k$ vecinos,$B$$k\geq\frac{n+1}2$. Deje $X=N(v)\cap B$$Y=N(v)\cap C$.

Un vértice de $Y$ no tiene un vecino en $X$ (que se completa un triángulo con $v$), así que se tiene en la mayoría de las $n-k$ vecinos,$B$. Pero entonces debe haber un $n+1-(n-k)=k+1$ vecinos,$A$, contradiciendo la elección de $v$. Contradicción.