# 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.

-
If I understand correctly, your condition forces the complement of the graph to have the degree of each vertex bounded by $2$. That means the complement graph can have at most $n$ edges, so $G$ has at least $(n^2 - n)/2 - n$ edges. This lower bound can be realized by the complement of an $n$-cycle (for large $n$). – ccc Nov 21 '11 at 13:21

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).$$
 Notice that all we needed was the fact that every induced graph on $4$ vertices contains at least $2$ edges. So, in effect, we are ignoring a lot of structure. – Srivatsan Nov 21 '11 at 16:25 Thank you. This lower bound is more than enough for me. – Gadi A Nov 22 '11 at 10:37