Does 3-partite graph with at least n+1 edges per vertex have a triangle? [closed]

I need help for one problem.

In every of 3 schools there are n students (in total = 3n vertex, n per school). Every student knows at least n+1 students from the other two schools. Prove that there are 3 students, one from each school, who know each other.

Do you have some idea for this proving?

Solution 1:

Let $G$ be a counterexample, i.e. a 3-partite graph with $n$ vertices in each partite set and minimum degree $n+1$ that has no triangle.

Let $v$ be a vertex that maximizes the number of neighbors it has in one partite set, say $k$. We may label the partite sets $A,B,C$, such that $v\in A$ and $v$ has $k$ neighbors in $B$. Since $k\leq n$, $v$ has at least one neighbor in $C$, say $w$.

$w$ has at most $n-k$ neighbors in $B$ (otherwise we find a triangle involving $v,w$ and a vertex of $B$), so $w$ has at least $(n+1)-(n-k)=k+1$ neighbors in $A$. This contradicts the choice of $v$.

Done.

(This problem awoke my interest in the sharpness question: is it true that for a given $n$ and even $k<3n(n+1)$ there always is a 3-partite graph with $n$ vertices in each partite set and total degree at most $k$ (and minimum degree at least $n$?) that has no triangle?)