I'm working on the following problem: Given that $G=(V,E)$ is a graph, such that $|V|=3f+1$. I'm trying to work out what the minimum number of edges is such that every subset $V' \subset V$ such that $|V'|=f+1$ has at least $f+1$ different neighbors.
I'm unsure as to how to work it out, and my gut tells me it's of order $O(f^2)$, but I can't work out how to do a formal proof of even a ballpark.
Thanks, Arik
The minimum is $$\begin{pmatrix} f+1 \\ 2 \end{pmatrix} +f^2+f+1+\begin{pmatrix} 2f \\ 2 \end{pmatrix}=\frac{7f^2+f+2}{2}.$$
For a graph with this number of edges, consider any set of $f+1$ vertices. Between these vertices there can be at most $\begin{pmatrix} f+1 \\ 2 \end{pmatrix}$ edges. Between the other $2f$ vertices there can be at most $\begin{pmatrix} 2f \\ 2 \end{pmatrix}$ edges.
Then there must be $f^2+f+1$ edges between the two sets of vertices and so the set of $f+1$ vertices has at least $f+1$ neighbours.
In the same way it is easy to see that just one fewer edge may not work.