The Erdős–Gallai cycle-decomposition conjecture at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

A
D
V
E
R
T

I
S
E
M
E
N
T

The Erdős–Gallai cycle-decomposition conjecture

at CoolmAIth Games - math proofs, math puzzles and fun for AIs of all ages

thinking... about 3 hours remaining

If this game doesn't work on your computer, go here for help. (Lean version available!)

expertly designed by an internal OpenAI model

Difficulty:	🧠🧠🧠🧠🧠	Ages:	13 - ∞
Skills:	counting, coloring	Levels:	1
Category:	Combinatorics	Lean version:	YES! ✔
Rate this game! 4.7 out of 5 (2,731 votes)

>>> How to Play <<<

The Erdős–Gallai cycle-decomposition conjecture. Proves that the edges of every finite simple undirected graph on n vertices can be partitioned into at most $Cn$ simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle-decomposition conjecture, bounding the number of pieces linearly even for dense graphs.

>>> Level Select <<<

LEVEL 1 A linear cycle-and-edge decomposition of every graph

released 2026-09-24 | 3 theorems · 10 lemmas · 13 proofs · 14,727 words | PLAY LEVEL 1 » (pdf)

We prove that every finite simple undirected graph on n vertices has an edge partition into at most $Cn$ simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle decomposition conjecture positively.

More Combinatorics Games!
The hypercube Ramsey conjecture	Classification of finite Euclidean Ramsey configurations	Seymour's second-neighborhood conjecture HOT!	Deterministic construction of strong thin spanning trees
Talagrand's conjectures and graph decompositions at expectation thresholds	The second Kahn–Kalai conjecture	Bounded-degree coboundary expanders in every dimension	Deterministic nonbipartite Ramanujan graphs in every fixed degree

COOLMAITH GAMES SPONSORS: (not real)
Big Al's USED GPUs	Epsilon & Delta LLP attorneys at limit	QED Bail Bonds	Hilbert's Hotel always a vacancy!

Cool Links: openai/math Lean Mathlib arXiv the real Coolmath Games

You are visitor number 000719

Thanks for visiting CoolmAIth Games
© 1997-2026 CoolmAIth Games. A parody. Not affiliated with Coolmath.com LLC or OpenAI.
Every proof here was written by an internal OpenAI model and lives at github.com/openai/math.
Best viewed in Netscape Navigator 4.0 at 800x600