Graph with $50$ vertices and $392$ edges with no $4$ independent vertices? I need an example of a graph with $50$ vertices and $392$ edges, with no independent set of size $4$. The graph should be loopless, and I think multiple edges are allowed. I don't know where to begin.
 A: Two copies of $K_{17}$, and a $K_{16}$. 
$17+17+16=50$ vertices and $136+136+120 = 392$ edges.
By the pigeonhole principle, of any $4$ vertices selected, two will be in the same $K$ graph and thus connected.
A: What would the complement of such a graph satisfy?
It would be a graph with $\binom{50}{2}-392=833$ and no $K_4$. By Turan's theorem the graph with the most edges and no $K_4$ is the complete 3-partite graph $K_{17,17,16}$, and it is unique up to isomorphism. This graph has exactly $17\cdot17+17\cdot16+17\cdot16=833$ edges.
So the only graph that works is the complement of $K_{17,17,16}$ which consists of two copies of $K_{17}$ and one $K_{16}$.
This method can be used to solve the problem in its generality. In other words if you want a graph on $n$ vertices and $e$ edges without independent sets of size $k$ take $k-1$ complete graphs such that the differences between their sizes is at most $1$ and such that the sum of their vertices is $n$, if this graph has more than $e$ edges then the graph you are looking for is unnatainable. Otherwise you can add edges untill you have $e$ edges and that graph will satisfy what you want. This can all be justified using Turan as I did for your example.
