Gallai's path decomposition in planar graphs

Alexandre Blanché, Marthe Bonamy, Nicolas Bonichon

In 1968, Gallai conjectured that the edges of any connected graph with $n$ vertices can be partitioned into $\lceil \frac{n}{2}\rceil$ paths. We show that this conjecture is true…