Suppose a tripartite, $(n+1)$-regular graph. Each one of its $3$ parts $(A,B,C)$ contains $n$ nodes. Show that the graph contains a triangle.
I think the fact that it is $n+1$ and not $n$ plays an important role because there will be at least an edge in both $B,C$ , let the edge `begins' from $A$.
I also tried to use the pigeonhole principle but I am lacking something. Any ideas?
Assume $G$ does not contain a triangle.
Let $A,B,C$ the three partite sets. Let $v$ be a vertex that maximizes the number of neighbours it has in one of the other partite sets (so no vertex have more neighbours in one single partite set than $v$).
By symmetry we may assume that $v\in A$, that $v$ has $k$ neighbours in $B$ and $k\geq\frac{n+1}2$. Let $X=N(v)\cap B$ and $Y=N(v)\cap C$.
A vertex of $Y$ cannot have a neighbour in $X$ (that would complete a triangle with $v$), so it has at most $n-k$ neighbours in $B$. But then it must have $n+1-(n-k)=k+1$ neighbours in $A$, contradicting the choice of $v$. Contradiction.