Question 29
Let $n \ge 2$ be an integer. Two players, Alice and Bob, play the following game: Initially all $\binom{n}{2}$ edges of the complete graph $K_n$ are uncolored. They take turns coloring edges red, with Alice starting first. In each move, a player selects one or two uncolored edges to color red, with the constraint that after each move, no three vertices can have all three edges between them colored red. The game ends when no more edges can be colored.
Prove that there exists a real number $\varepsilon \gt 0$ such that for any integer $n \ge 2$, no matter how Bob plays, Alice can ensure that at the end of the game, the number of red edges does not exceed $\left(\frac{1}{4} - \varepsilon\right)n^2 + n$.
Prove that there exists a real number $\varepsilon \gt 0$ such that for any integer $n \ge 2$, no matter how Bob plays, Alice can ensure that at the end of the game, the number of red edges does not exceed $\left(\frac{1}{4} - \varepsilon\right)n^2 + n$.