This is a question I've [implicitly asked on AoPS five years ago](http://artofproblemsolving.com/community/c6h427146p2418487), and has not been answered. I apologize for its possible simplicity, as I am not a graph theorist.



> 
> Let $n$ and $k$ be two positive integers. Let $G$ be a graph with vertex set $V$. Assume that $V$ is partitioned into $k$ disjoint subsets $V\_1, V\_2, \ldots, V\_k$, each of which has exactly $n$ elements (so that $\left|V\right| = nk$). Assume that for each $i \in \left\{1, 2, \ldots, k\right\}$, the set $V\_i$ is an independent set of $G$ (that is, no two vertices of $V\_i$ are connected by an edge). Assume also that each vertex of $G$ has degree $\geq \left(k-2\right)n+1$.
> 
> 
> Prove or disprove that $G$ has a $k$-clique (that is, $k$ distinct vertices pairwise connected by edges).
> 
> 
> 


This is a triviality when $k = 1$ or $k = 2$, and a known contest problem in the case when $k = 3$ (see <http://artofproblemsolving.com/community/c6h40982> , and <http://artofproblemsolving.com/community/c6h49347> for an extension which is not completely true as stated). In my AoPS thread linked above, I have asked whether the $k = 4$ case is true, but of course the real question is the general case.



Turan-like bound for $k$-partite graphs
It is not true in general that $G$ under your conditions contains a $k$-clique. For example, if $k = 4$ consider the following construction by Gouping Jin (see the proof of Theorem 3.1 in [1]):


Let $V\_i = A\_i \cup B\_i$ for $i \in \{1,2,3,4\}$, where $\left|A\_i\right| = \lfloor n/3 \rfloor$ and $\left|B\_i\right| = n - \lfloor n/3 \rfloor$. Join vertices so that the following pairs of sets induce complete bipartite subgraphs: $(A\_1,V\_2 \cup B\_3 \cup B\_4)$, $(A\_2,V\_1\cup B\_3 \cup B\_4)$, $(A\_3,V\_4\cup B\_1 \cup B\_2)$, $(A\_4,V\_3 \cup B\_1 \cup B\_2)$ and $(B\_1 \cup B\_2, B\_3 \cup B\_4)$ (i.e. join every vertex of $A\_1$ with every vertex of $V\_2 \cup B\_3 \cup B\_4$, and so on). The resulting graph, $H\_n$, is clearly $4$-partite and it is not difficult to see that it has minimum degree $\delta(H\_n) = \lfloor (2 + 1/3)n \rfloor$. Furthermore, $H\_n$ contains no $4$-clique. Now, since $\lfloor (2 + 1/3)n \rfloor \geq (4-2)n + 1$ for $n \geq 3$ this gives us examples of graphs that satisfy your conditions but do not contain a $4$-clique.


In fact, Jin shows in [1] that the best lower bound (to guarantee a $k$-clique) on the degrees of a $k$-partite graph with each part of size $n$ is $\lfloor (2 + 1/3)n \rfloor + 1$ for $k = 4$, $\lfloor (3 + 1/3)n \rfloor + 1$ for $k = 5$ and $\leq \left(k - 1 - \frac{1}{1 + 1/2 + 1/3 + \dots + \frac{1}{k-2}} \right)n + 1$ for all $k \geq 4$.


[1] G. Jin, "Complete Subgraphs of $r$-partite Graphs", Combinatorics, Probability and Computing 1, (1992), 241-250.


