66th Belarusian Mathematical Olympiad

(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 .$$