Papex

Open problem · Mathematics · Open

Erdős Problem #583

Can every connected graph on n vertices be partitioned into at most ⌈n/2⌉ edge-disjoint paths?

Summary

A problem of Erdős and Gallai on splitting the edges of a graph into paths, known as Gallai's path decomposition conjecture.

AI-assisted claims

Partial result claimed · 04 Oct 2026

Gallai's conjecture with two exceptional even vertices

“Let F be the subgraph induced by the even-degree vertices of a connected finite simple graph G on n vertices, and let h and x be distinct vertices of F. Suppose every other vertex of F has degree at most three in F. Then for each of h and x there is an edge partition into at most ⌈n/2⌉ simple paths, at least two of which end at that vertex. Consequently, Gallai's bound holds whenever at most two vertices of F have degree greater than three.”

By
Idris Ali Shaik
AI involvement
OpenAI Codex and other AI tools assisted with mathematical exploration, Lean formalization, and manuscript preparation. The author reviewed the AI-assisted material and takes full responsibility for the manuscript.
Model
OpenAI Codex, as stated
Where
Zenodo
Formal proof
Lean 4, published by the source
Repository
shaikidris/gallai-two-exception at 5f4130a · read 21 Nov 2026
Palomar
PALOMAR-2026-10-04-000006 v1
Source last read
19 Nov 2026

Checks

1 Palomar entry

  • 04 Oct 2026 · In Palomar · Palomar: Palomar entry PALOMAR-2026-10-04-000006 v1: shaikidris/gallai-two-exception at commit 5f4130a, theorems Gallai.Submission.prescribed_endpoint, Gallai.Submission.ceiling_bound, Gallai.Submission.simultaneous_floor_add_one and 1 more. Source

Claims as their sources state them. Listing a claim is not a check by Papex; the status stays the source’s.

All AI-assisted claims

Source

Open, as listed by Erdős problems database (github.com/teorth/erdosproblems), status "falsifiable" · erdosproblems.com. Checked 19 Nov 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics