Given a simple undirected connected graph. What is the minimum number of edge-disjoint paths needed to cover all edges of the graph? I have only found information about the vertex-covering one.
My friend suggests that such value equals u/2, with u being number of vertices with odd degree, or 1 if there is no such vertices.
Can anyone confirm if his assumption is correct or not?