(Solution by Y. Dubovik, L. Manzhulina, I. Pchalintsau, B. Serankou.)
First, for the sake of convenience, we reformulate the problem as follows. Any
two of $n$ vertices of the graph ($n \ge 4$) are connected with an edge either of
red or of blue color. It is known that for any two vertices there exists a vertex
connected to both the vertices with blue edges. Find the maximum number of
red edges (or, equivalently, the minimum number of blue edges) in the graph.
We find the minimum number $k$ of blue edges then the maximum number of
red edges is $\frac{n(n-1)}{2} - k$. In the
figures blue edges are shown, all
the absent edges are red. These
figures show that the minimum
number of blue edges cannot be
greater than $k = n - 1 + \lfloor \frac{n}{2} \rfloor$.
Show that this number is indeed
the smallest possible. We call the
number of blue edges containing
a vertex a degree of this vertex. If the degrees of all the graph vertices are at least 3, then the total number of blue edges is at least $k_1 = \frac{3n}{2} > k$. So we may assume that there is a vertex $A$ of degree 2. Let $AB$ and $AC$ be the corresponding blue edges. Applying the problem condition to $A$ and $B$, we conclude that $B$ and $C$ are certainly connected with blue edge. Let $M$ be the set of remaining (other than $A$, $B$, $C$) vertices. Then any vertex from $M$ must be connected with blue edge either to $B$ or to $C$. For any vertex from $M$ we mark this edge. From the problem condition it follows that in addition to marked edges at least one blue edge should outgo from any vertex of $M$.
The number of these additional edges is not less than $\lfloor \frac{n-2}{2} \rfloor = \lfloor \frac{n}{2} \rfloor - 1$.
Therefore there are at least
$3 + n - 3 + \lfloor \frac{n}{2} \rfloor - 1 = n - 1 + \lfloor \frac{n}{2} \rfloor$
blue edges as was claimed.

n is odd

n is even

So, the maximum number of the red edges is
$$\frac{n(n-1)}{2} - (n-1) - \lfloor \frac{n}{2} \rfloor = \frac{(n-2)(n-1)}{2} - \lfloor \frac{n}{2} \rfloor .$$