---

Claim. Theorem 0 of L. Pyber, Covering the edges of a connected graph by paths, J. Combin. Theory Ser. B 66 (1996), 152--159 (p. 152): a graph on $n$ vertices each of whose cycles contains a vertex of odd degree can be covered by at most $\lfloor n/2\rfloor$ edge-disjoint paths. A cover by edge-disjoint paths uses every edge once, so it is a path decomposition, and the hypothesis says that the vertices of even degree induce a forest. No connectedness is assumed. The paper derives the theorem (p. 155) from its Corollary 1.2 and Lovász's theorem, and its Example (p. 153), $K_{2m+1}$ minus $m-1$ independent edges, shows the bound is best possible. The issue is that of January 1996 and prints no day, so the page is dated by the issue month. The theorem is recorded on the theorem page of the source card.

Covers. The statement of Problem 583 for connected graphs each of whose cycles contains a vertex of odd degree (the even-degree vertices induce a forest), with $\lfloor n/2\rfloor$ paths.

Depends on. Nothing in this wiki.

Acceptance. Refereed: the paper is a publication in the Journal of Combinatorial Theory, Series B. The site's curator credits the result while labeling the problem FALSIFIABLE, which is commentary on an open problem and not reviewed evidence.