On path decompositions of 2k-regular graphs

Tibor Gallai conjectured that the edge set of every connected graph G on n vertices can be partitioned into ⌈n/2⌉ paths. Let Gk be the class of all 2k-regular graphs of girth at least 2k−2 that admit a pair of disjoint perfect matchings. In this work, we show that Gallai's conjecture holds in Gk for each k≥3. Indeed, we show a stronger statement which claims that each graph in Gk on n vertices has a partition of their edge set into n/2 paths and cycles, where the length of each path is in {2k−1,2k,2k+1} and cycles are of length 2k.