Decomposing a graph into paths Given a simple graph with $n$ vertices, show that you can remove all edges in $O(n\log n)$ rounds, where in each round you are allowed to remove all edges of any (single) path.
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.