0
$\begingroup$

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?

1 Answers 1

2

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.

  • 0
    @Heisenberg: I still don't see how that's supposed to imply the conclusion. I suggest that you work through that idea and if you think you have a complete proof you can write it down and then it will be easier to check than these tentative ideas.2012-11-05