Minimum number of edge-disjoint paths needed to cover a graph 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? 
 A: Assuming that the "paths" we're talking about are actually trails, that is, walks that may repeat vertices but may not repeat edges (which seems to be the most natural context for requiring them to be edge-disjoint), that sounds right to me.
Clearly at least that many paths will be needed, and it's not too difficult to see that you can construct a covering at set of exactly that many paths greedily:


*

*Start at an odd-degree vertex, and walk along random unused edges until you there's nowhere you can go. At that time you must have reached another odd degree vertex.

*Continue doing this as long as there are odd-degree vertices left.

*If there are still unused edges in the graph, locate a vertex that is touched by both used and unused edges. Break one of the paths you have already identified through that vertex, and start walking randomly along unused edges from there. Since you've used up all of the odd vertices, the only place you can end is at the vertex where you started, so you can then proceed along the rest of the original path, so the number of paths doesn't increase.

*Repeat until all edges have been covered.
A: In a directed graph, we can transform this into a flow problem with each edge having the lower-bound capacity of $1$ and all link to a source and a sink with edges with lower-bound capacity $0$. The least number of paths will be the minimum flow value. Is this idea correct and if so can it be generalized to 'undirected graph'? 
