# Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time

I am stuck with the following exercise:

Is it possible to decide whether a given flow $$f$$ is a unique mamimum flow in $$O(\lvert V \rvert + \lvert E \rvert)$$ time?

I am not sure that this is possible.

I understand that we can check in $$O(\lvert V \rvert + \lvert E \rvert)$$ time whether $$f$$ is maximal. (Just build the residual graph $$G_f$$ and check whether there is an augmenting path. This takes $$O(\lvert E \rvert)$$ time.) But I do not see how to check the uniqueness. Could you please give me a hint?

Edit: Now I have an idea: If we can show that $$f \text{ is unique } \Longleftrightarrow \text{ there are no cycles in G_f containing the source s or the sink t}$$ we are done.

The direction $$\Longrightarrow$$ is trivial: If there was a cycle in $$G_f$$ containing $$s$$ or $$t$$ we can pump the flow through this cycle or leave it out with no consequences, so $$f$$ is not unique.

But I have no idea how to do the other part. However, I discovered the following theorem that might be useful for this: The "Flow Decomposition Theorem". According to these notes it says:

Any feasible flow $$f$$ can be decomposed into at most $$m$$ cycles and $$s-t$$ paths with non-zero flows. The value of $$f$$ is equal to the sum of flows over the paths.