Consider a graph with $n$ vertices such that if one takes any 4 vertices there are at most 4 edges among these 4 vertices (Notice that there are 6 "possible" edges among these 4 vertices). What is the maximum possible edge density for such a graph as a function of $n$ and what is the limit as $n$ goes to infinity?


Using a probabilistic argument one can show that as $n$ goes to infinity that the edge density can be at most $\frac{2}{3}+\epsilon$, yet finding such a construction seems extremely tricky. 



Minimum Edge Density given a particular condition
It is well-known, but I do not know where did it appear for the first time.


The answer is $f(2k)=k^2$ for $n=2k$ and $f(2k+1)=k(k+1)$ for $n=2k+1$. Examples are bipartite graphs $K\_{k,k}$ and $K\_{k,k+1}$. The proof of upper estimate goes by induction. Base $n=4$ is clear. Assume that $n\geqslant 5$ and graph on $n-1$ vertices may have at most $f(n-1)$ edges. Assume that some graph $G$ on $n$ vertices has at least $f(n)+1$ edges. Remove some edges so that exactly $f(n)+1$ edges remain. Each vertex $v$ has degree at least $f(n)-f(n-1)+1$, else $G\setminus v$ has more than $f(n-1)$ edges. Thus total number of edges is not less than $n(f(n)-f(n-1)+1)/2>f(n)+1$ (check this for two cases). The contradiction.


