Minimum number of edges There are $9$ points. Each pair of points are connected by a third point. That is, for all point pair $(A, B)$, there exists $C$ such that $AC$ and $CB$ are connected. What's the minimum number of edges in the undirected graph?
I don't have idea on how to start this problem. Seems like coloring points won't work. Appreciate any help!
 A: The answer of this problem is $12$.
The example of the $12$-edge graph satisfying the condition is following. It shapes like a windmill.

Now we prove that we cannot construct such graph with $\leq 11$ edges. Let $d_1, d_2, \dots, d_9$ be the degree of each vertex. To satisfy the condition, the graph must hold both of the following:

*

*$d_i \geq 2$ for all $i$.

*$\frac{d_1(d_1-1)}{2} + \frac{d_2(d_2-1)}{2} + \cdots + \frac{d_9(d_9-1)}{2} \geq 36$.

And then we should minimize $d_1 + d_2 + \cdots + d_9$, which equals (the number of edges) * 2.
The optimal strategy of this minimization problem is "to choose only one $d_i$ to increase, and set the others to be $d_i = 2$", because we want to increase "sum of quadratics" as soon as possible. This yields the optimal answer $d = (8, 2, 2, 2, \dots, 2)$, which is $d_1 + d_2 + \cdots + d_9 = 24$ so it means $12$ edges.
It means that we need at least $12$ edges for satisfying condition 1. and 2. So, if we prove 1. and 2., then we can conclude that the graph with $\leq 11$ edges is impossible.
Proof for (1): Suppose that $d_u = 0$ for some $u$. If we choose $A = u$, there is no candidate for $C$, so the condition will not hold. Suppose that $d_u = 1$ for some $u$. Let $v$ the only adjacent vertex of $u$. If we choose $A = u$ and $B = v$, there is no candidate for $C$ (because $C \neq B$ and $C$ must be adjacent to $A$), so the condition will not hold. Thus, $d_i \geq 2$ must hold for all vertices.
Proof for (2): Suppose that a vertex $u$ has degree $d_u$. If we choose $C = u$, there are $\frac{d_u(d_u-1)}{2}$ available pairs of $(A, B)$. Since we need at least one $C$ for all vertex pair $(A, B)$, the sum of that "available pairs" must be at least $\binom{9}{2} = 36$. Thus, the inequality (2) must hold.
Supplement: Additional Fact
This case is $n = 9$, but we can calculate the exact optimal answer for all $n$.

*

*When $n$ is odd, the optimal answer is $\frac{3}{2}n - \frac{3}{2}$. The example is a windmill-like graph, which joins triangles into one central vertex.

*When $n$ is even, the optimal answer is $\frac{3}{2}n - 1$. The example is also a windmill-like graph, but a pair of triangle "shares" one edge (to make the number of vertices even).

The proof of this fact can be done as above, that is writing necessary conditions of $d_i$'s and calculate the lower bound. If $n$ is odd, the optimal degree sequence is $(n-1, 2, 2, \dots, 2)$, and if $n$ is even, the optimal degree sequence is $(n-1, 3, 2, \dots, 2)$.
