$G$ on $mn$ vertices has a $K_{n+1}$ as a subgraph. Let $G$ be a simple graph on $mn$ vertices where each vertex has degree strictly greater than $m(n-1)$.
Then is it true that $G$ has a $K_{n+1}$ as a subgraph?
I tried with contradiction but stuck.
 A: Let $E$ be the set of edges and $v_i\in V$ be the vertices of $G$.
By Handshaking Lemma we get $$2|E|=\sum_{i=1}^{mn}\deg(v_i)>mn(mn-m)=m^2n(n-1)\implies |E|>\frac{1}{2}m^2n(n-1)$$.
Assume that $G$ is $K_{n+1}$ free, but then by Turan's Theorem we have $|E|<\frac{1}{2}m^2n(n-1)$ which is a contradiction.
A: This is quite a bit easier than Turán's theorem. It is easy to see from first principles that any maximal clique in $G$ must have at least $n+1$ vertices. Perhaps it is even easier to see it we restate it in terms of the complementary graph $\overline G$. If every vertex in $G$ has degree greater than $m(n-1)$, then every vertex in $\overline G$ has degree less than $(mn-1)-m(n-1)$, i.e., less than $m-1$. We have to show that a maximal independent set in $\overline G$ has at least $n+1$ vertices. Restating this in simpler notation:
Theorem. If $G=(V,E)$ is a graph of order $|V|=mn$, and if every vertex of $G$ has degree less than $m-1$, then every maximal independent set in $G$ has at least $n+1$ vertices.
Notation. $N[v]$ denotes the closed neighborhood of a vertex $v$, i.e., $N[v]=\{v\}\cup\{w:vw\in E\}$.
(So $|N[v]|\lt m$.)
Proof. Suppose $S$ is a maximal independent set in $G$. Then $\bigcup_{v\in S}N[v]=V$,
so
$$mn=|V|=\left|\bigcup_{v\in S}N[v]\right|\le\sum_{v\in S}|N(v)|\lt|S|\cdot m,$$
so $n\lt|S|$, i.e., $|S|\ge n+1$.
Remark. Provided $m\gt1$, the assumption $|V|=mn$ can be weakened to $|V|\gt(m-1)n$.
