---

Claim. L. Lovász, On covering of graphs, Theory of Graphs (Proc. Colloq., Tihany, 1966), 1968, 231--236, proves that every graph on $n$ vertices decomposes into at most $\lfloor n/2\rfloor$ paths and cycles; a graph with at most one vertex of even degree then decomposes into at most $\lfloor n/2\rfloor$ paths. The paper is known here only as it is quoted: Pyber (p. 152 of his 1996 paper) gives the case in which every vertex has odd degree, and Chu, Fan and Zhou state it as their Theorem 1.2 (p. 1), for graphs connected or not with at most one vertex of even degree; Bonamy and Perrett, Anto and Basavaraju, and Fan quote it the same way. The volume prints no day, so the page is dated by its year.

Covers. The statement of Problem 583 for connected graphs with at most one vertex of even degree, with $\lfloor n/2\rfloor$ paths.

Depends on. Nothing in this wiki.

Standing. Claimed: a proceedings volume is not refereed evidence, and the site's curator credits the result while labeling the problem FALSIFIABLE, which is commentary on an open problem and not reviewed evidence.