Erdős Problem #583
Can every connected graph on n vertices be partitioned into at most ⌈n/2⌉ edge-disjoint paths?
Summary
AI-assisted claims
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.
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.