What is the minimum number of edges in a 10-vertex graph where any 5 vertices have at least 2 edges between them?
Let $f(n)$ denote the minimum number of edges that must be drawn in a graph with $n$ vertices so that any 5 vertices have at least 2 edges between them. The task is to determine $f(10)$.

We claim that

$$
f(n+1) \geq \frac{n+1}{n-1} f(n)
$$

Suppose in a graph with $n+1$ points, any 5 vertices have at least 2 edges between them, and the number of edges in the graph is exactly $f(n+1)$. Remove the vertex with the highest degree and the $k$ edges emanating from it; this results in an $n$-point graph with $f(n+1)-k$ edges, in which any 5 points still have at least 2 edges between them, hence it must have at least $f(n)$ edges. The sum of the degrees in the $n+1$-vertex graph is twice the number of edges: $2 f(n+1)$, so $k \geq \frac{2 f(n+1)}{n+1}$. Summarizing the above,

$$
f(n) \leq f(n+1)-k \leq f(n+1)-\frac{2 f(n+1)}{n+1}
$$

which, rearranged, gives

$$
f(n+1) \geq \frac{n+1}{n-1} f(n)
$$

From this, with $f(5)=2$, we have $f(6) \geq \frac{6}{4} f(5)=3 ; \quad f(7) \geq \frac{7}{5} f(6) \geq 4.2$, hence $f(7) \geq 5 ;$ $f(8) \geq \frac{8}{6} f(7) \geq 6.66 \ldots$, hence $f(8) \geq 7 ; f(9) \geq \frac{9}{7} f(8) \geq 9 ; f(10) \geq \frac{10}{8} f(9) \geq 11.25$, hence $f(10) \geq 12$.

The graph shown in the figure has 10 vertices and 12 edges, and we show that any 5 vertices have at least 2 edges between them. The graph consists of three components: a complete graph with 4 vertices and two complete graphs with 3 vertices each. If we select 5 vertices, either there will be three among them that belong to the same component, and then there will be three edges between them, or we will select two vertices from two components and one from the third, in which case there will be two edges between the pairs of vertices selected from the same component.

Thus, the minimum number of edges is 12.

Remark. It can be shown using the method described that for any $n$, the minimum number of edges can be achieved if the graph is the union of three complete graphs, where the number of vertices in these graphs differs by at most 1.
![](https://cdn.mathpix.com/cropped/2024_05_02_0021399a37570fed77f5g-1.jpg?height=212&width=896&top_left_y=1414&top_left_x=606)