Solved with eisirrational. Let $n=3333$. The answer is $15n=49995$. We prove a more general statement: if $G$ is a graph with $an$ vertices so that any $3n$-vertex subgraph contains at least $3n$ edges, then the minimum possible number of edges in $G$ is $\tbinom a2n$. Equality is achieved by $n$ copies of $K_a$. To see that this works, suppose that in some $3n$-vertex subgraph, we select $b_i$ vertices in the $i$th copy of $K_a$. Then the number of edges of the $3n$-vertex subgraph is \[\sum_{i=1}^n\binom{b_i}2\ge n\binom32=3n\]by Jensen's inequality. We now prove the lower bound. Let $f(k)$ denote the minimum number of edges in a graph of $k$ vertices such that any $3n$-vertex subgraph has at least $3n$ edges. Claim: For all $k$, \[\frac{f(k+1)}{k+1}\ge\frac{f(k)}{k-1}.\] Proof. Consider a graph with $k+1$ vertices and as few edges as possible, so it has $f(k+1)$ edges. Each of the $k+1$ subgraphs of $k$ vertices has at least $f(k)$ edges, and each edge is a member of $k-1$ of these subgraphs, thus the claim is true by double counting. $\blacksquare$ Note that for each $k$, \[f(k+1)-f(k)\ge\frac{2f(k)}{k-1}\]by Claim 1, but also \[\frac{f(k+1)}k>\frac{f(k+1)}{k+1}\ge\frac{f(k)}{k-1},\]so $f(k)/(k-1)$ is strictly increasing. Claim: $f(an)\ge\tbinom a2n$. Proof. We induct on $a$. The base case $a=3$ is given. Assume the claim holds for $a$. Then if $M\ge an$, \[f(M+1)-f(M)\ge\frac{2f(M)}{M-1}\ge\frac{2\cdot\binom a2n}{an-1}>a-1,\]so $f(M+1)-f(M)\ge a$. Then \[f\big( (a+1)n\big)-f(an)\ge\sum_{i=an}^{(a+1)n-1}\big(f(i+1)-f(i)\big)\ge an,\]whence \[f\big( (a+1)n\big)\ge f(an)+an\ge\binom a2n+an=\binom{a+1}2n,\]as claimed. $\blacksquare$ Thus $f(6n)\ge15n$, and we are done.

Here is a much easier way to get the lower bound. Let $A$ be a subset of $V(G)$ of size $m = 9999$ with the number of edges in its induced subgraph minimal (at least $m$ by assumption). Then, let $\deg_A(v)$ denote the number of neighbors of $v$ that are in $A$. Let $B = V(G)\setminus A$. We will show that for all $b\in B, \deg_A(b) \geq 3$. If $b\in B, a\in A$ with $\deg_A(b) < \deg_A(a)$, then swapping $a,b$ decreases the number of edges in $A$, contradiction. Thus, \[ \deg_A(b) \geq \max_{a\in A} \deg_A(a). \]In particular, if $\deg_A(a)\geq 3$ for some $a\in A$, we are done. Otherwise, assume $\deg_A(a) \leq 2$ for all $a\in A$. Then, since $\sum\limits_{a\in A} \deg_A(a) = 2m$, we must have $\deg_A(a) = 2$ for all $a\in A$, and $\deg_A(b) \geq 2$ for all $b\in B$. It follows that every vertex in $b$ has a neighbor $a_b$ in $A$. If $\deg_A(b)\leq 2$, then since $\deg_A(a_b) = 2$, swapping $b$ with $a_b$ would decrease the number of edges (it would replace $2$ edges with $\deg_A(b)-1$ edges) in $A$, contradiction. Thus, $\deg_A(b)\geq 3$ for all $b\in B$, and so there are at least $3n$ edges in the cut between $A,B$. Since each of $A,B$ has $n$ edges, this gives us $5n$ total edges. $\Box$

Seems identical to the above but ok Let $3n = 9999$ be an arbitrary multiple of three. We claim that the answer is $15n = 49995$. The construction is as follows: consider $n$ cliques of size $6$. This clearly has $\binom{6}{2}n=15n$ edges. Now if we pick $c_1, c_2, c_3, \dots, c_n$ vertices for $\bar G$ in each clique, then we have \[ \binom{c_1}{2} + \binom{c_2}{2} + \dots + \binom{c_n}{2} \ge n \binom{\tfrac{3n}{n}}{2} = 3n.\]by Jensen's. Now let $\mathcal G$ be an arbitrary vertex subset of size $3n$. Let $C(v)$ be the number of vertices in $\mathcal G$ connected with $v$. Say there exists some $u \not\in \mathcal G$ such that $C(u) < 3$, and $C(v) < 3$ for all $v \in \mathcal G$ as well. Then by the hypothesis $C(v) = 2$ for all $v \in \mathcal G$. Now notice that the induced subgraph of $\mathcal{G} \setminus \{v\}$ has exactly $3n-2$ edges for all $v \in \mathcal G$, hence for all such $v$, $u$ must be the endpoint of two edges in the induced subgraph of $\{u\} \cup \mathcal{G} \setminus \{v\}$ for the hypothesis to hold. Hence $C(u) > 0$, so by picking $v$ as one of the vertices in $\mathcal G$ connected to $u$, we must have $C(u) \ge 3$, contradiction. Now if there exists $u \not\in \mathcal G$ such that $C(u) < 3$, there must exist $v \in \mathcal G$ such that $C(v) \ge 3$. It follows that we can simply continuously swap all such $u$ with some $v$ until for all $u' \in V(G) \setminus \mathcal G$, $C(u') \ge 3$. Now there must be at least $3 \cdot 3n = 9n$ edges between vertices in $\mathcal G$ and vertices in $V(G) \setminus \mathcal G$, hence by the hypothesis on the induced subgraphs of the aforementioned vertex sets, we have that there are at least $3n + 9n + 3n = 15n$ vertices, as desired. $\blacksquare$

I like oranges The answer is $5 \cdot 9999$. This is achievable by creating $3333$ groups of $6$ vertices, then for each $6$ vertices we make a clique of size $6$. Then, if $a_{1}$ vertices were selected from the first clique, $a_{2}$ from the second, and so on, the number of edges is \[\sum_{i=1}^{3333} \binom{a_{i}}{2} \geq 3333\binom{\frac{a_{1} + a_{2} + \ldots a_{3333}}{3333}}{2} = 3333\cdot \binom{3}{2} = 9999\]so each subset of $9999$ vertices has at least $9999$ edges. Now we prove this is minimal. Consider the subset $S$ of $9999$ vertices such that the number of edges in $S$ is minimal, and let the number of edges be $k$. First, assume there exists a vertex $V\in\S$ such that $V$ has at least $3$ neighbors in $S$ (we will deal with the other case later). Furthermore, let $T = G\backslash S$. Now, for each vertex $U\in T$, consider the subset $(S\backslash V)\cup U$. There are at most $k-3$ edges in $S\backslash V$, and since $k$ is minimal, this means there are at least $3$ edges between $U$ and $S\backslash V$. Doing this for all $U$ gives at least $3\cdot 9999$ edges between vertices in $T$ and vertices in $S$. Since the number of edges in $T$ is at least $k$, the total number of edges is at least \[|S| + |T| + 3\cdot 9999 \geq 2k + 3\cdot 9999\geq 5\cdot 9999\]This proves that there are at least $5\cdot 9999$ edges. Now, we just need to consider if vertex $V\in \S$ has $2$ neighbors in $S$. This means the number of edges in $S$ is exactly $9999$. Again, let $T = G\backslash S$. For every vertex $U\in T$, if the number of edges from $U$ to $S$ is less than $3$, then take $V\in S$ such that $V$ is a neighbor of $U$. Then, consider the set $(S\backslash V)\cup U$. By removing $V$, we remove $2$ edges, and since there are at most $2$ edges from $U$ to $S$, but one of them is $UV$, we will add at most $1$ edge back, so we will have at most $9998$ edges, a contradiction. Thus, for all $U\in T$, there are at least $3$ edges from $U$ to $S$. The total number of edges is at least \[|S| + |T| + 3\cdot 9999 \geq 9999 + 9999 + 3\cdot 9999 = 5\cdot 9999\]Thus, for this case, there is also at least $5\cdot 9999$ edges. We conclude that $5\cdot 9999$ is minimal.

We solve the following equivalent statement: Canada 2020/5, Alex Song wrote: Let $N=9999$. Graph $G$ has $2N$ vertices and any induced subgraph of $G$ on $N$ vertices has at least $N$ edges. At least how many edges does $G$ have? Solution with lots of help from awang11. We claim that $G$ has at least $5N$ edges. For construction: split $G$ into $N/3$ copies of $K_6$, which yields $5N$ edges and satisfies the property on induced subgraphs by Jensen's Inequality on $\binom n2$. Now we deal with the meat of the problem: showing $|V(G)|\ge 5N$. Let $S$ denote the induced subgraph of $G$ with $N$ vertices and with the fewest edges. Let $T=G\setminus S$. Let $v$ be the vertex in $T$ with the fewest edges from it to $S$, so there are at most two such edges or we are done. We claim this latter case cannot occur. So the assumption is that $\deg v$ restricted to $S\cup \{v\}=S'$ is at most $2$. Then either $\deg_{S'} v = 0$ in which case we have a contradiction by swapping $v$ with an arbitrary vertex of $S$ having nonzero degree, or we can note that some vertex $u$ in $S$ has degree at least $\frac{2N+1}{N}>2$ in $S'$ and swap $u$ with $v$ for contradiction.

For simplicity let $n = 9999$. I claim our answer is $5n = 49995$. This can be achieved by having $\tfrac n3$ copies of $K_6$. Indeed, we may check that for any subgraph $G' \subseteq G$ with size $n$, with $a_i$ vertices from the $i$-th clique, that\[|E(G')| = \binom{a_1}{2} + \ldots + \binom{a_{n/3}}{2} \geq \frac n3 \binom{3}{2} = n\]by convexity. Next, we show $|E(G)| \geq 5n$ necessarily must hold true. Suppose we partition $G$ into $H$ and $H'$, each with size $n$. It remains to show that such a partition exists where the number of edges between $H$ and $H'$ are $\geq 3n$. Consider the following process, where when we refer to degree, it is always about the induced subgraph of $H'$ on $G$. Take the vertex in $H$ with least degree and swap it with the vertex in $H'$ with the greatest degree $-$ as long as $|E(H')| > n$, the sum of $\text{deg} (v)$ across all $v \in H'$ is $> 2n$ and by pigeonhole there is a vertex with degree $\geq 3$. This way, we are purging the vertices in $H$ with small degree and replacing them with vertices with $\geq 3$ degree. This process can continue until $|E(H')| = n$, at which point we will prove all vertices in $H$ have $\geq 3$ degree. Suppose some vertex $v \in H$ still has $\leq 2$ degree. It must have exactly degree $2$, else we can swap $v$ with any vertex in $H'$ with degree $2$ (clearly existent since average degree across $H'$ is $2$) and cause $|E(H')| < n$. Furthermore, every vertex in $H'$ must have degree $2$, else we can swap a degree $\geq 3$ vertex with $v$ and again cause $|E(H')| < n$. Say $v$ is connected to $u \in H'$ and $u$ is connected to $u_1, u_2 \in H'$. Now, we can consider the graph $(H' \backslash u) \cup v$ with size $n$ - upon removing $u$, we remove some $2$ edges, and upon adding $v$, we add back one edge since the other is $vu$. Then $|E((H' \backslash u) \cup v)| < n$, a contradiction. In summary, given any partition of $G$ into $H, H'$, we may swap vertices between them to get a desirable partitions where the edges between them is at least $3n$, for a total of\[|E(G)| = |E(H)| + |E(H')| + |E(H \to H')|\geq n + n + 3n = 5n\]edges indeed. $\blacksquare$

Replace $19998$ with $6n$; I claim that the answer is $15n$, achieved by $n$ copies of $K_6$. To prove that the given construction works, suppose that we choose $a_1,a_2,\ldots,a_n$ vertices from each $K_6$. Then, we have that $$\sum \binom{a_i}{2}>n\cdot \binom{3}{2}=3n$$by Jensen's. Now, suppose FTSOC that $G$ has less than $15n$ edges, but each of its $3n$ vertex subgraph contains $3n$ edges. Consider the subgraph $H$ with the least number of edges; since both $H$ and $G\setminus H$ contain at least $3n$ edges, there are less than $9n$ edges between $H$ and $G\setminus H$. By pigeonhole, there exists a vertex $v$ in $G\setminus H$ connected to at most two vertices in $H$. If any vertex in $H$ has internal degree at least $3$, we can replace it with $v$ to obtain a $3n$-vertex subgraph containing less edges than $H$, contradicting $H$'s optimality. Hence, each vertex in $H$ must have internal degree $2$. However, then we can swap $v$ with a neighbor in $H$ to obtain a $3n$-vertex subgraph containing less than $3n$ edges.

The answer is $9999 \cdot 5$. In general, replacing $9999$ with $3n$, we show that the answer is precisely $15n$. Construction is to take disjoint $6$-cliques. For the bound, consider the subgraph $H$ of $G$ with a minimal number of edges. Set $k$ to be the maximum degree in $H$. Then for any $u \in G \setminus H$, $u$ must be connected to at least $k$ vertices in $H$, so there are $nk$ edges between $G$ and $H$. If $k \geq 3$ we are done immediately. On the other hand, if the maximum degree is at most $2$, $H$ must be precisely a cycle. Furthermore, there exists a vertex $v \in G \setminus H$ connected to exactly two vertices in $H$. Then, remove any $u \in H$ that is not connected to exactly those two vertices. We obtain a new subgraph $H'$ that still has $3n$ edges but now contains a vertex of degree at least $3$, so we can repeat the previous argument.

Easy one.