A stronger Flow Decomposition Theorem?

Question

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?

Thank you!

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.

Answer 1

The statement of Ahuja, Magnanti, and Orlin applies to general flows, not only $(s,t)$-flows. During decomposition, when removing a path flow, either one of the two endpoints become balanced or one the arcs will get flow 0. This gives the bound $m+n$.

In the case of $(s,t)$-flows, we may note that during decomposition the nodes $s$ and $t$ becomes balanced at the same time. This gives the already the bound $m+1$ on the number of paths and cycles. If we look at the flow decomposition, when finding the final path flow (this is where the balance of $s$ and $t$ becomes balanced), if no flow on some arc is made 0, it means that we will still find a cycle flow. Now the final cycle flow will make at least two arcs have flow 0 at the same time. This sharpens the bound to $m$ in case of $(s,t)$-flows.

P.S. The proofs of the notes you link are not quite correct, see the comments.