---

Claim. A. Blanché, M. Bonamy and N. Bonichon first posted the result as the extended abstract Gallai's path decomposition for planar graphs, Extended Abstracts EuroComb 2021 (Trends in Mathematics), 758--764, online on 24 August 2021 (the claim's date), whose abstract states that every connected planar graph except $K_3$ and $K_5^-$ ($K_5$ minus one edge) decomposes into $\lfloor n/2\rfloor$ paths. The full paper, Gallai's path decomposition in planar graphs, arXiv:2110.08870 (v1 17 October 2021; v2 21 June 2022, 95 pp.), states it as Theorem 1.1, every connected planar graph on $n$ vertices decomposes into $\lceil n/2\rceil$ paths, and Theorem 1.2, $\lfloor n/2\rfloor$ paths except for $K_3$ and $K_5^-$, which still meet $\lceil n/2\rceil$. The theorems are recorded, from the arXiv v2, on the Theorem 1.1 page and the Theorem 1.2 page of the source card.

Covers. The statement of Problem 583 for connected planar graphs.

Depends on. Nothing in this wiki.

Standing. Claimed: no journal version of the full paper has been found, and an extended abstract in a proceedings volume is not refereed evidence. The site's curator credits the result while labeling the problem FALSIFIABLE, which is commentary on an open problem and not reviewed evidence.