Decomposing a graph into paths
A classical result of Lovász (On covering of graphs) states that a graph on $n$ vertices can be decomposed into at most $n/2$ paths and cycles, and so into at most $n$ paths.