# Extremal graph. $2n$ vertices in which every subgraph of $n$ vertices has $k$ edges. Lower bound on the number of edges

Assume that a simple graph has $$2n$$ vertices and the property that every subset of $$n$$ vertices induces a subgraph with at least $$k$$ edges.

Question: What lower bounds are known on the total number of edges?

For example, if $$k=n$$, then the graph should have at least $$5n$$ edges.

We can see this by splitting the set of vertices into two disjoint sets $$V_1,V_2$$ such that $$V_2$$ induces a subgraph with minimum number of edges. Denote by $$d_2(v)$$ the number of edges of $$v$$ connecting it to a vertex of $$V_2$$.

If $$v_1\in V_1$$ and $$v_2\in V_2$$ we have that $$d_2(v_1)\geq d_2(v_2)$$, otherwise we can make $$v_1,v_2$$ switch subsets and make $$V_2$$ have less edges.

Assume that there is $$v_1\in V_1$$ with $$d_2(v_1)\leq 2$$. Then all $$v_2\in V_2$$ will have $$d_2(v_2)\leq 2$$. This gives at most $$n$$ edges in the graph induced by $$V_2$$ with equality only if $$d_2(v_2)=2$$ for all $$v_2\in V_2$$. Therefore, if $$d_2(v_1)\leq2$$ we must have $$d_2(v_1)=2$$ and $$d_2(v_2)=2$$ for all $$v_2\in V_2$$. But then switching $$v_1$$ and one of its $$V_2$$ adjacent vertices we degrease the number of edges in the graph induced by $$V_2$$.

Therefore, $$d_2(v_1)\geq 3$$ for all $$v_1\in V_1$$. This implies that we must have $$n$$ edges in the graph induced by $$V_1$$, also $$n$$ edges in the graph induced by $$V_2$$ and at least $$3n$$ edges going from vertices in $$V_1$$ to vertices in $$V_2$$. In total $$5n$$ edges.