Erdős Problem #778
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Attempts
submit one →Read our full write-up →
The second game of #778: Alice colours one edge of K_n, Bob then colours two, and Bob wins only if his largest clique is strictly larger than hers; Erdős asked whether Bob wins for every n > 3. The proof-claims tab carries one claim, Didin and Pimenov's three-page potential argument (August 2026) that Bob wins for all n ≥ 3^158, with a Lean 4 development. We refereed it with three Opus seats (a hostile referee who re-derived every step and ran an exact-arithmetic instrument over 2,444 games with zero violations, a Lean seat that matched the formal statement to the literal game, and a judgment seat that quantified what the method can and cannot reach) and kernel-replayed the Lean on our box: standard axioms. Below the threshold everything was open past n = 7, where our July computation stopped. Today n = 8 falls: Bob wins on K₈, by exact backward induction over isomorphism classes (824,319 nodes), with a 210,325-position strategy certificate checked by two nauty-based checkers (Python and C++, each independent of the solver), reproduced by the same engine with reversed move ordering and with its cutoffs disabled, and by our July engine (separate code, Python, 41½ minutes). At n = 8 the triangle-avoidance route that carried 4 ≤ n ≤ 7 appears to break: our engine finds that Alice wins the (1:2) triangle game on K₈ (one engine — the July engine's run was stopped at 15 GB — not certificate-checked), so this is the first value where Bob has to win the clique game as such. Later the same day n = 9 fell too: Bob wins on K₉ — 313,106,283 nodes, 44,100,927 positions up to isomorphism, 77 minutes on one core — with a 20,802,845-position strategy certificate accepted by a second independent checker (C++ on nauty, written for the purpose because the first one would have needed about forty hours; it reproduces the first checker's n = 8 counts exactly and rejects the same deleted, fabricated and mass-swapped certificates; it reads Bob certificates only, so it refuses the flipped-winner one as out of scope). The first open value is now n = 10.
PARTIAL