Erdős Problem #778
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: graph theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Erdős described three games in which two players claim the edges of a complete graph. In the main game, Alice and Bob alternately colour edges red and blue. Alice goes first and wins only when her final red graph has a strictly larger clique than Bob's blue graph; a tie is a Bob win.
Erdős asked whether Bob always wins for \(n\geq3\). He also asked a biased game where Bob takes two edges per Alice edge but must achieve a strictly larger clique, and a game comparing maximum vertex degrees instead of clique sizes. These are three different questions. None is fully settled at its original parameters.
A small example
On \(K_3\) there are three edges. With one edge claimed per turn, Alice gets two and Bob gets one. Each graph contains an edge but neither contains a triangle, so each has clique number two. Therefore Bob wins through the tie rule, regardless of the order in which available edges were selected.
This is a valid result for \(n=3\) only. In the biased game, the winning tie condition differs, so the same reasoning cannot simply be reused to decide it.
What is known
Alexandru Malekshahian and Sam Spiro, On a clique-building game of Erdős, arXiv:2410.18304v2 (5 May 2026), define the games and prove several partial results. Their Theorem 1 shows that Bob wins the ordinary clique game for a set of \(n\) having asymptotic density at least \(3/4\). More concretely, if Alice can win at \(n\), then Bob can win at \(n+1,n+2,n+3\). This conclusion is not victory for every \(n\).
Their Theorem 2 treats the maximum-degree (star) game: Bob wins for a set of \(n\) of density at least \(2/3\), using ana\logous three-consecutive-parameter reasoning. Theorem 3 of version 2 concerns the biased game. In particular, for sufficiently large \(n\) Bob can win when Alice claims one edge per turn and Bob claims four, rather than the two edges proposed by Erdős.
A central subtlety is the tie convention. In the unbiased clique game, Alice must strictly beat Bob; in the biased game where Bob claims more edges, Bob must strictly beat Alice. Reversing the convention would reverse several small-case outcomes and invalidate a strategy-stealing argument.
The paper uses a strategy-stealing and dimension-extension mechanism: hypothetical Alice victories at a smaller order force Bob victories at nearby larger orders. This yields density statements, not a uniform proof.
GCL's current state
The original authenticated RESULT/1 source return records BOUNDED_TASK_DESIGNED and retains the original mathematical qualifications. This is an editorially reviewed explanatory article in the EC-BULK-005-R9 protected batch, effective only when that exact-hash transaction merges. The corresponding maintained Erdős statement and its bibliography were inspected. This editorial decision does not certify any full original theorem proof, independent external formalization, or Lean kernel check.
Preserved source-review qualifications: open three game variants distinct; bob clique density 3 4 star density 2 3. See the immutable 128-case critical review record for the complete source-return caveats.
What remains
Implement a bounded finite minimax solver for \(K_3\) and \(K_4\) that assigns each edge to the actual player on their scheduled turn, evaluates clique and degree scores only after the game ends, and uses the correct tie priority for each variant. Keep the biased \((1,2)\) and \((1,4)\) cases separate. Review the original Guy 1983 statement before treating any later game variant as identical.
Sources and claim boundaries
- Erdős problem #778; authenticated original source audit.
- A. Malekshahian and S. Spiro, On a clique-building game of Erdős, arXiv:2410.18304v2 (5 May 2026), Definitions and Theorems 1–3, pp. 1–3.
Editorial source decision: R9 critical review, REVIEWED as a source-grounded explanation only. All open mathematical questions, primary-proof fidelity obligations, and external formalization caveats remain separate.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2049 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.