Decompose a flow network into several trivial flows

105 Views Asked by At

Let $f$ be a flow in (a directed) network $G$. Show that it is possible to express $f$ as a sum of another flow $f_0$ which value is 0, and at most $|E|$ flows, each of which is trivial - i.e. flows only on a single path from the source to the sink.

This is what I tried: choose $f_i$s where the value of each $f_i$ is the minimal value of $f$ along the path of $f_i$, and then choose $f_0$ to complete the sum of the $f_i$s to be identical to $f$. But I'm not sure how to show that $f_0$ is indeed a flow.