Track / Stage 5 / 128 of 400 #1208 of 2444

Problem 1208

AIME late

Combinatorics Difficulty 5.3 Prove it Berkeley Math Circle: Monthly Contest 4 · United States

A simple graph $G$ on $2020$ vertices has its edges colored red and green. It turns out that any monochromatic cycle has even length. Given this information, what is the maximum number of edges $G$ could have?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

Solution:

Note that $G$ has no $K_{5}$ ; indeed, it's well-known that the only triangle-free coloring of the edges of $K_{5}$ consists of two monochromatic $5$ -cycles. Therefore, the number of edges of $G$ is at most $\binom{4}{2} \cdot 505^{2} = 1530150$ by Turán's theorem.

To show this occurs, we split the graph into four equally sized components $A, B, C, D$ . We color red all edges between $A$ and $B$ , or $C$ and $D$ . We color green all edges between $A$ and $C$ , $A$ and $D$ , $B$ and $C$ , and $B$ and $D$ . This indeed has the claimed number of edges, and the subgraphs formed by each color are bipartite, so this solves the problem.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.