A lower bound on the number of edges in a graph satisfying a "subset matching" property Given a graph on $n$ vertices, I wish to find a lower bound on the number of edges required before the graph can has the following property: Every subset of 4 vertices contains a matching. 
Put more formally, for every $v_1,v_2,v_3,v_4\in V$ we have that either $(v_1,v_2), (v_3,v_4)\in E$ or $(v_1,v_3),(v_2,v_4)\in E$ or $(v_1,v_4),(v_2,v_3)\in E$ (more edges are ok as well).
My intuition says the lower bound will be $\Omega(n^2)$; if it is lower it will be very interesting for me.
 A: Here's a quick approach that gives an $\Omega(n^2)$ answer but the bound is not quite as strong as what ccc's comment claims. The main advantage of this approach is its simplicity and generality. 
Pick $4$ vertices at random without replacement. Then for any fixed edge $e = xy$ of $G$, we are interested in the probability that $e$ is observed by the sample. Heuristically, we want to sample both $x$ and $y$, so this happens with probability $O(\frac{1}{n^2})$. However, we can also make a more rigorous estimate as follows. Of the four vertices, one of them is $x$ and another is $y$; fixing these positions can be done in $4 \cdot 3$ ways. Once these positions are fixed, the probability that these positions contain $x$ and $y$ respectively is $\frac{1}{n} \cdot \frac{1}{n-1} = \frac{1}{n(n-1)}$ (assuming $n \geqslant 4)$. Summing over all the $12$ possibilities for the positions (they are all disjoint), the probability that the edge is seen by the sample is $\frac{12}{n(n-1)}$. 
Therefore, by linearity of expectations, the expected number of edges within the sample is equal to $\frac{12m}{n(n-1)}$, where $m := |E|$. Lower bounding this by $2$ (since every $4$-tuple of vertices contains a matching), we get
$$
\frac{12m}{n(n-1)} \geqslant 2  \quad \implies \quad m \geqslant \frac{1}{6} n(n-1).
$$
