Gallai's Conjecture For Graphs of Girth at Least Four

In 1966, Gallai conjectured that for any simple, connected graph G having n vertices, there is a path‐decomposition of G having at most ⌈ n 2 ⌉ paths. In this article, we show that for any simple graph G having girth g ≥ 4 , there is a path‐decomposition of G having at mostp ( G ) 2 + ⌊ ( g + 1 2 g ) q ( G ) ⌋paths, where p ( G ) is the number of vertices of odd degree in G and q ( G ) is the number of nonisolated vertices of even degree in G .