What is the smallest number of roads in a country?

There are $300$ cities in the country. Some pairs of them are connected by roads. It turned out that if you close any $150$ cities, then there will be at least $150$ roads. What is the smallest number of roads in a country?

My solution:

We take a graph with $2n$ vertices such that each $n$-vertex subgraph of it contains at least $n$ edges. Let us sum this number over all possible $n$-vertex subgraphs. The resulting number will be greater or equal to $nC_{2 n}^{n}$. Note that for each edge there are exactly $C_{2 n-2}^{n-2}$ $n$-vertex subgraphs containing it. So each existing edge appears in the sum exactly $C_{2 n-2}^{n-2}$ times. Thus, the number of roads (edges of the original graph) is greater than or equal to $\dfrac{2 n(2n-1)}{n-1}$. Therefore, the answer is $603$.

However, this is an estimate, but is there an example of such a graph with $300$ vertices?

For $4$ vertices this is an impossible situation (one cannot draw $2$ edges between $2$ vertices).

For $6$ vertices, the inequality will exactly give the number of edges in the complete graph.

For $8$, the inequality will give: ($⩾8\cdot7/3=18.6666$).

I think we can try to build a graph with $8$ vertices and $19$ edges that satisfies the properties that any $4$-vertex subgraph has at least $4$ edges. But how to do this is another question. Any ideas?

For fixed $n$, you can solve the problem via integer linear programming as follows. Let $N=\{0,\dots,2n-1\}$ be the node set, and let $E=\{(i,j)\in N \times N: i < j\}$. Let binary decision variable $x_{i,j}$ indicate whether edge $(i,j)\in E$ appears. The problem is to minimize $$\sum_{(i,j)\in E} x_{i,j}$$ subject to linear constraints $$\sum_{(i,j)\in E: \{i,j\} \subset S} x_{i,j} \ge n \quad \text{for all $S\subset N$ such that $|S|=n$}.$$

For $2n=8$, the minimum turns out to be $23$:

{<0,1>,<0,3>,<0,4>,<0,5>,<0,6>,<0,7>,<1,3>,<1,4>,<1,5>,<1,6>,<1,7>,<2,3>,<2,4>,<2,5>,<2,6>,<2,7>,<3,4>,<3,6>,<3,7>,<4,6>,<4,7>,<5,6>,<5,7>}