Minimum number of edges in a graph with $2n$ vertices such that each subgraph with $n$ vertices has at least $n$ edges?

As answered by Ross, your bound is not tight. Since no one is posting a tight solution, I'll show the order is correct. Specifically I'm gonna prove the following statement. (I'm always assuming $n$ even, but the same holds true with floors)

Proposition. For every $n$ large enough there exist graphs on $n$ vertices, at most $10n$ edges such that every set of size $n/2$ has at least $n/2$ edges.

Consider $G(n,p)$ for $p=18.4/n$, we'll show that

1. w.h.p. $G(n,p)$ has less than $10n$ edges
2. w.h.p every subset of size $n/2$ has at least $n/2$ edges

Both are easy consequences of Chernoff's inequality. To prove (1) notice that $$\mathbb E[e(G(n,p))]=p\binom n2=9.2(n-1)\leq 9.2n$$ therefore, by Chernoff \begin{align}\mathbb P(e(G(n,p))\geq10n)&\leq\exp\left(-cn\right)\\\\&\to0\end{align} for some explicit constant $c>0$. This proves property (1). To show property (2) let $S$ be a fixed subset of size $n/2$. Then $\mathbb Ee(S)=p\binom{n/2}2=(2.3+o(1))n$. Therefore, by Chernoff \begin{align}\mathbb P(e(S)\leq n/2)&\leq\exp\left(-(1+o(1))\left(\frac{18}{23}\right)^22.3n/2\right)\\\\&\leq\exp\left(-\frac{16}{23}n\right)\end{align} now, the probability that there exists such an $S$ is bounded by \begin{align}\mathbb P\left(\exists S:|S|=n/2,\;e(S)\leq n/2\right)&\leq\sum_{S:|S|=n/2}\mathbb P(e(S)\leq n/2)\\\\ &\leq\binom n{n/2}\exp\left(-\frac{16}{23}n\right)\\\\&\leq\exp\left(\left(\log 2-\frac{16}{23}\right)n\right)\\\\&\to0\end{align}

since $16/23>\log 2$. Therefore we have property (2) and so there exists graphs with both properties at the same time. This approach can actually be pushed until $Cn$ edges for $C=2+4\sqrt{(1+\log2)\log 2}+\log16\approx9.1$. So this, together with the observation that your bound gives $(2+o(1))n$ shows that (after replacing all $n$'s by $2n$)

$$4n\leq\min\{e(G):G\subset K_{2n},\;\text{every }n\text{-set has at least }n\text{ edges}\}\leq2Cn$$ where between $4$ and $2C\approx 18.21$ the correct constant lies, is probably hard to show, unless there's a relatively natural construction, as is the case with most questions about designs. My guess is that probably $4$ is the correct constant

When $n$ is a multiple of $3$, there is a $2n$-vertex graph $G$ with only $5n$ edges that has the property we want: a union of $n/3$ copies of $K_6$.

To see this, suppose we select an $n$-vertex subset of $V(G)$ such that for $0 \le k \le 6$, there are $n_k$ copies of $K_6$ with $k$ vertices selected from them. Then:

• The total number of vertices in the subset is $v = n_1 + 2n_2 + 3n_3 + 4n_4 + 5n_5 + 6n_6$;
• The total number of copies of $K_6$ is $c = n_0 + n_1 + n_2 + n_3 + n_4 + n_5 + n_6$;
• The number of edges in the induced subgraph is $m = n_2 + 3n_3 + 6n_4 + 10n_5 + 15n_6$.

Solving a dual linear program, I found that $$2v - 3c = -3n_0 - n_1 + n_2 + 3n_3 + 5n_4 + 7n_5 + 9n_6$$ is a lower bound on $m$. (All the coefficients are smaller than the corresponding coefficient in $m$.) But we also know that $v=n$ and $c = n/3$, so $2v - 3c = n$ and therefore any $n$-vertex subset induces at least $n$ edges.

We can extend this strategy to all $n\ge 3$ with a slightly worse bound, as follows:

• When $n \equiv 1 \pmod 3$, take $(n-1)/3 - 1$ copies of $K_6$ and one copy of $K_{2,2,2,2}$. (This has $5n+4$ edges total.)
• When $n \equiv 2 \pmod 3$, take $(n-2)/3 - 1$ copies of $K_6$ and one copy of the complement of the Petersen graph. (This has $5n+5$ edges total.)

Suppose $H$ is the "oddball" graph that we end up selecting; let's say that we choose $h$ vertices of $H$ and $n-h$ vertices from the rest. Then the same bound of $2v-3c$ still applies to the edges induced by vertices selected from the copies of $K_6$; however, this time, $v = n-h$ and $c \in \{\frac{n-4}{3}, \frac{n-5}{3}\}$. In total, we end up getting $n-2h+4$ or $n-2h+5$ edges in the respective cases, and so we are done if we check that:

• Choosing any $h$ vertices from $K_{2,2,2,2}$ induces at least $2h-4$ edges.
• Choosing any $h$ vertices from the complement of the Petersen graph induces at least $2h-5$ edges.

I checked these by brute force in Mathematica (which is also how I found the two graphs to begin with).

In fact, I believe that replacing $K_{2,2,2,2}$ by the $23$-edge graph in this answer will suffice, reducing the bound in that case to $5n+3$. The $23$-edge graph lacks one property that seems important: taking $3$ vertices from it does not always induce $2\cdot 3 - 4$ edges. However, if we only take $3$ vertices from it, we need to take $n-3$ vertices from the $\frac{n-4}{3}$ copies of $K_6$: more than half. In this case, we can squeeze out an extra edge: the bound $2v-3c$ is tight only if $n_0, n_1, n_4, n_5, n_6$ are all $0$, which cannot get enough vertices.

For $n=4$, the bound in your attempt gives $e\ge 19$. We can improve this bound to $23$, which is tight, as conjectured by @Calvin Lin (His intuition is great)

Lemma 1. Any graph $G$ with chormatic number $\chi$ has $e(G)\ge \binom{\chi}{2}+|G|-\chi$.

edges bound using chromatic number

I suggest that you can read the proof of the lemma before reading the answer below. I do not use the lemma directly, but I got my idea from the proofs inside the link.

Let $G$ be a graph, with the minimum number of edges, on $8$ vertices and any subgraph induced by $4$ vertices has $\ge 4$ edges. For two disjoint subset $A,B$ of $V(G)$, let $e(A,B)$ denote the number of edges between $A,B$.

Lemma 2. If $G$ contains two disjoint independent sets of size $2$, say $A$ and $B$, then $e(A,B)=4$.

Lemma 3. The maximum independent set in $G$ has size $\le 2$. The chromatic number $\chi$ of $G$ is at least $\frac{n}{2}=4$.

Case 1. $\chi=4$. We have $e(G)\ge \binom{4}{2}4=24.$

Case 2. $\chi=5$. Let $A=\{1,2\},B=\{3,4\},C,\{7\},\{8\}$ be a $5$-coloring. Then $e(A\cup B\cup C,\{7\})\ge 5$, since if $1$ and $3$ (it can not be $1$ and $2$ by lemma 3) are not adjacent to $7$, then $\{1,2,3,7\}$ induces $\le 3$ edges. In addition, there is an edge between $7,8$, since $\chi\neq 4$. We have $$e(G)\ge e(A,B)+e(B,C)+e(C,A)+e(\{7\},\{8\})+2\times 5 \\ \ge 3\times 4+1+10=23.$$

Case 3. $\chi = 7$. Let $A=\{1,2\}$, $\{3\},...,\{8\}$ be a $7$-coloring, then we claim that $e(A,\{3,...,8\})\ge 11.$

If $e(A,\{3,...,8\})\le 10$, assume that $13\notin E(G)$. Then $14\in E(G)$ since $\chi = 7$, and for any $i\in \{4,...,8\}$, we have $e(A, \{i\})=2$, otherwise the subgraph induced by $\{1,2,3,i\}$ has $\le 3$ edges. So $e(A,\{3,...,8\})\ge e(A,\{3\})+\sum_{i=4}^8e(A,\{i\})=1+2\times5=11$, contridict to it $\le 10$

In addition, the graph induced by $\{3,...,8\}$ is a complete graph since $\chi=7$. We have $e(G)\ge e(A,\{3,...,8\})+e(\{3,...,8\})\ge 11+\binom{6}{2}= 26$.

Case 4. $\chi=6$. In this case, Let $A=\{1,2\},B=\{3,4\},\{5\},\{6\},\{7\},\{8\}$ be its $6$-coloring. Then $e(A,B)\ge 4$ and $e(\{5,6,7,8\})=6$ (since they form a $4$-clique.)

Assume $1$ and $4$ are adjcaent to all vertices in $\{5,6,7,8\}$ (since otherwise we can get a $5$-coloring).

We claim that $e(\{2\},\{5,6,7,8\})\ge 3$. If $\le 2$, assume $5,6$ are not adjacent to $2$. Then $\{1,2,5,6\}$ induces $\le 3$ edges.

So $e(G)\ge 4+6 +4\times 2+3\times 2=24$

Here is a graph corredponding to case 2 and shows that the bound $23$ is tight.

Last time I did the first improvement on the upper bound; now, to kickstart work on the lower bound; I'll do the first improvement over OP's bound. Let

$$f(n):=\min\{e(G):G\subset K_{2n},\;\text{every }n\text{-set has at least }n\text{ edges}\}$$

Joining Misha's and OP's bounds, we know $$4n+3\leq f(n)\leq 5n+c_n\leq 5n+5$$ where $c_n\in\{0,4,5\}$ depends only on $n$ modulo $3$. I'll prove that $f(n)=4n+\omega(1)$, in other words, there's no constant $C>0$ such that $f(n)\leq 4n+C$ for every $n$. We'll proceed by contradiction, notice that WLOG we may assume for every $n$ there exists $G$ on $2n$ vertices with the desired property and $e(G)=4n+C$ for $C\in\mathbb Z_{\geq 0}$.

Proposition 1. Under the assumptions above, we have $\Delta(G)\leq C+2$

Proof. Suppose $\Delta(G)\geq C+3$, then, let $v\in G$ be such that $\deg(v)=\Delta(G)$, looking at $G-v$ (which still has the property) we get \begin{align}4n+C&=e(G)\\&=\Delta(G)+e(G-v)\\&\geq\Delta(G)+n\cdot\frac{\binom{2n-1}{n}}{\binom{2n-3}{n-2}}\\&\geq C+3+4n-2\\&=4n+C+1\end{align} which is a contradiction.

Consider now the following process, $G=G_{0}\supset G_1\supset\cdots\supset G_{k+1}$ where $G_{i+1}=G_i-v_i$ where $\deg_{G_i}(v_i)=\Delta(G_i)$. After $k$ steps we know $$e(G)=\sum_{i=0}^{k}\Delta(G_i)+e(G_{k+1})$$ We'll pick $k$ maximal such that $\Delta(G_k)\geq 4$ and bound $e(G_{k+1})$ counting edges in $n$-sets.

Proposition 2. If $i\leq\displaystyle\frac{2n-1}{2C+1}$ then $\Delta(G_i)\geq 4$

Proof. Notice that the maximum degree of a graph is at least its average degree, and so \begin{align}\Delta(G_i)&\geq\frac{2(e(G)-\Delta(G_0)-\cdots-\Delta(G_{i-1}))}{2n-i}\\&\geq\frac{2(4n+C-i\Delta(G))}{2n-i}\\&\geq\frac{8n+2C-2i(C+2)}{2n-i}\\&>3\end{align} where the last inequality follows by our choice of $i$; therefore $\Delta(G_i)\geq 4$

Now, setting $k=\left\lfloor\frac{2n-1}{2C+1}\right\rfloor=\frac{2}{2C+1}n+O(1)$ we get \begin{align}e(G)&=\sum_{i=0}^{k}\Delta(G_i)+e(G_{k+1})\\&\geq4(k+1)+n\cdot\frac{\binom{2n-k-1}{n}}{\binom{2n-k-3}{n-2}}\\&\geq\left(4+\frac{4}{(2C+1)^2}\right)n+O(1)\\&> 4n+C\end{align} for $n$ large enough, which is a contradiction.

This bound can actually give you a lower bound on the asymptotic term (i.e. the $\omega(1)$) if you follow the calculations carefully and optimize over $C$, if my quick calculations are right, you should be able to show any $C=o(n)$, but I doubt it can give a linear improvement. Now I don't actually have a guess for which constant should be true. Another thing you may try, is now continue the process not while $\Delta(G_i)\geq 4$ but while $\Delta(G_i)\geq 3$ or even $\Delta(G_i)\geq 2$. I have not done this and I don't know whether it will be able to give a linear improvement (but I doubt it)

This is a response to Bruno Andrades's answer. I improve the lower bound on his constant from $4$ to $5$.

If we have a graph of $n$ vertices and $ne_0$ edges, the average number of edges per vertex is $e_0$, so the average order of a vertex is $2e_0$ (as each edge connects to two vertices). Hence there must be at least one vertex with order $\lceil 2e_0 \rceil$. We can take a greedy approach, removing the vertices with the highest order one at a time to find an induced subgraph with a small (but not necessarily minimal) number of edges.

When we do this, at each step the number of edges removed is at least $\lceil 2e_0 \rceil$ until the average order of a vertex drops to $2e \le \lceil 2e_0 \rceil - 1$. The average number of edges will repeatedly drop, and the average that we arrive at after removing $\frac{n}{2}$ vertices determines the number of edges in the induced subgraph, so I will find a lower bound on how quickly the average falls, to upper bound how large it can end up.

If we start with $ne_0$ edges and remove $\lceil 2e_0 \rceil$ of them $k$ times we end up with $ne_0 - k \lceil 2e_0 \rceil$ edges for an average order of $2 \frac{ne_0 - k \lceil 2e_0 \rceil}{n-k}$, which drops to $\lceil 2e_0 \rceil - 1$ when $$2 \frac{ne_0 - k \lceil 2e_0 \rceil}{n-k} \le \lceil 2e_0 \rceil - 1$$ $$\iff n(2e_0 - \lceil 2e_0 \rceil + 1) \le k (\lceil 2e_0 \rceil + 1)$$ $$\iff k \ge \frac{n(2e_0 - \lceil 2e_0 \rceil + 1)}{\lceil 2e_0 \rceil + 1}$$ so the first $k$ where this occurs is $$k = \lceil \frac{n(2e_0 - \lceil 2e_0 \rceil + 1)}{\lceil 2e_0 \rceil + 1} \rceil$$ which is an upper bound on how long it can take for the average order to fall to $\lceil 2e_0 \rceil - 1$. For each subsequent drop from an integer $2e = a$ to $a-1$ it takes at most $$k = \lceil \frac{n'}{a + 1} \rceil$$ $$\le \frac{n'}{a + 1} + 1$$ steps, where $n'$ is the number of remaining vertices when the average order first reaches $\le \lceil 2e_0 \rceil$.

We know the average order of a vertex has to end up $\ge 2$, so working backwards the number of steps taken for it to fall from $3$ to $2$ was at most $$k = \frac{\frac12 n + k}{a + 1} + 1$$ as the starting number of vertices $n' = \frac12 n + k$ for the number of remaining vertices to be $\frac12 n$ after $k$ are removed. Solving for $k$, we get $$k = \frac{n}{2a} + \frac{a+1}{a}$$ $$\le \frac{n}{2a} + 2$$ $$= \frac{n}{2 \cdot 3} + 2$$ Call it $\frac16 n$ plus a finite constant for simplicity. Then similarly, the number of steps taken to go from $e = 4$ to $3$ is $\frac16$ plus a constant, as is the number of steps taken to go from $5$ to $4$. So, for large $n$, the lower bound on the average order of the vertices that you would need to start with at $n$ vertices to end up with an average order of $2$ at $\frac12 n$ vertices is almost exactly $5$. As $n \to \infty$ it limits to $5$.

Translating to instead talk about a graph with $2n$ vertices, this means it would have to start with $5n$ edges for the induced subgraph of size $n$ our greedy approach selects to end up with $n$ edges, which improves the lower bound on the constant from Bruno Andrades's answer from $4$ to $5$. It is now my turn to conjecture $5$ is the true value of the constant.

I am a bit tired currently, hopefully I will find time to rewrite this later for intelligibility.