# Circulations in Digraphs

Let G be a digraph and $\phi$ be a circulation, $\phi(e) \ge 0$ an integer, i.e.,

$\displaystyle\sum\limits_{e\in\delta^{-}(v)} \phi(e) = \displaystyle\sum\limits_{e\in\delta^{+}(v)} \phi(e), \; \; \forall \; v \in V(G)$

Prove that there exists a set of directed cycles $C_{1}, C_{2},....,C_{n}$ (not necessarily unique) such that $\forall \; e \in E(G)$:

$\phi(e) = |\{i: 1 \le i \le n, \; e \in E(C_{i})\}|$

I'm not quite sure what is supposed to be meant by the last line. Does it mean that $\phi(e)$ is equal to the number of times $e$ appears in the given cycle?

-

No, it can't mean that, because the index on the cycle is not "given" but a bound variable in that expression. It means that $\phi(e)$ is the number of cycles $C_i$ in which $e$ occurs.
This only holds if your definition of a circulation includes, beyond what you've written, that $\phi(e)$ is a non-negative integer.
Ah sorry about that. Yes, $\phi(e)$ is indeed a non-negative integer. – Heisenberg Nov 5 '12 at 15:53
Added. :) I am still confused about the question because the following might be a counterexample? Consider the directed cycle on 3 edges, and assign to each edge the value 4. In this graph there are 3 directed cycles in which any $e$ occurs, but $\phi(e) = 4 \gt 3$. – Heisenberg Nov 5 '12 at 16:00
@Heisenberg: I don't see where you added it. It only says that $\phi(e)\ge0$. – joriki Nov 5 '12 at 16:36
@Heisenberg: I don't understand what you mean by "In this graph there are $3$ directed cycles in which any $e$ occurs". On the one hand, that graph has only one directed cycle, not $3$; and on the other hand, there's no requirement for the cycles $C_i$ to be distinct. In that example, the assertion is validated by $C_1$ through $C_4$ all given by the only cycle in the graph. – joriki Nov 5 '12 at 16:38