Problem dossier · Graph Decompositions
Gallai's path decomposition conjecture
The edges of every connected graph on n vertices can be decomposed into at most ⌈n/2⌉ paths.
§1
Status
Open. Known for graphs whose vertices of even degree form a forest (Lovász-derived), planar graphs (Blanché–Bonamy–Bonichon 2021 announcement), and other classes.
Think you can crack this one? Read the playbook before you announce →
§2
The Angle of Attack
Exhaustively verify small graphs; implement decomposition heuristics and study which graphs need exactly ⌈n/2⌉ paths — the tight family drives the induction.
Tags: path decomposition · edges · connected graphs
§3
The Lab
No instruments built yet. When this problem gets tackled, its interactive instruments — explorers, searches, verifiers running in the browser — live here. See the Collatz dossier for what a fully tackled problem looks like.
§4
The Log
Empty. Work on this problem gets logged here as dated entries — constructions tried, code run, dead ends included. Dead ends are results.
§5
Related Problems
More open problems in Graph Decompositions and adjacent territory.
- 1-Factorization conjecture — Graph Decompositions
- Erdős–Sós conjecture — Graph Decompositions
- Linear arboricity conjecture — Graph Decompositions
- Overfull conjecture — Graph Decompositions