In the classic Network Flows: Theory, Algorithms, and Applications book (pages 80/81) the flow decomposition theorem is stated as follows:
Every nonnegative arc flow x can be represented as a path and cycle flow (though not necessarily uniquely) with the following two properties:
(a) Every directed path with positive flow connects a deficit node to an excess node
(b) At most n+m paths and cycles have nonzero flow; out of these at most m cycles have nonzero flow with m the number of edges and n the number of nodes in the graph
My question is, if the theorem can be formulated more strongly modifying point b as follows:
(b) At most m paths and cycles have nonzero flow
My question arises as going through the lecture nodes of a more modern optimization course at Stanford, I find the flow decomposition theorem formulated exactly with this "stronger" assertion (page 58 with proof here or a similar theorem here).
Going through the proofs in the lecture nodes and the book, I find the stronger formulation justified. Especially in Network Flows: Theory, Algorithms, and Applications the following argument is given for their m+n bound on paths:
Now observe that each time we identify a directed path, we reduce the excess/deficit of some node to zero or the flow on some arc to zero;
As I understand it, reducing the excess/deficit of some node to zero implies setting the flow on some arc to zero, as the excess/deficit flow of a node has to go/come over an arc whose flow is now set to zero. This however would imply bounding the number of paths with m instead of n+m, as each construction of a flow-path would remove one edge and not one edge or node from the graph.
Have I misunderstood the proof and are the lecture nodes from Stanford wrong? Do you know other books which one could possible cite for the stronger version of the flow decomposition theorem?
Note: In this question with the very promising title, a different question has been asked. It took the theorem from one of the aforementioned Stanford notes, and in the answers the correctness of it was discussed albeit for different reasons.