Breakthrough Tracker record

A preprint proves the Erdős–Gallai cycle-decomposition conjecture

Kim proves that the edges of every n-vertex graph can be decomposed into O(n) cycles and single edges, equivalently that every Eulerian n-vertex graph decomposes into O(n) cycles.

← Back to the filtered Breakthrough Tracker

Stable ID: math-erdos-gallai-cycle-decomposition-2026
Revision: math-erdos-gallai-cycle-decomposition-2026.v1
Field: Mathematics · Extremal graph theory and combinatorics
Evidence: Tier 1 · Peer reviewed: No
Record state: Provisional · Preprint proof with a separate formalized route
Last checked: 2026-10-19

AI role

Kim reports extensive assistance from ChatGPT and Claude while retaining responsibility for the proof. A separately developed OpenAI route is AI-generated and Lean-formalized.

Record details

Problem or result: Erdős–Gallai cycle decomposition of graph edges
Authors: Jaehoon Kim
Institutions: Korea Advanced Institute of Science and Technology
Result date: First submitted October 6 and revised October 9, 2026

Why it matters

The result settles the asymptotic cycle-decomposition conjecture and supplies a second proof route separate from the formalized OpenAI announcement.

Limits

This does not prove the sharp Hajós bound; it establishes the required linear-order decomposition. Both proof routes are recent preprints, and formal verification of one encoding is not peer review of either mathematical exposition.

Sources

Primary: Kim proof of the Erdős–Gallai conjecture, version 2
Independent formal route: OpenAI mathematics repository

Correction and revision history

2026-10-19 — Added after primary-source, scope, status, AI-role and limitation review.

Machine-readable: JSON v1 · CSV v1 · Schema v1

This individual record remains noindex until a story-specific featured image passes Kingy’s rendered-pixel visual review. The source-linked tracker hub remains the public index.