Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
up vote 1 down vote accepted

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.

share|cite|improve this answer
Ah sorry about that. Yes, $\phi(e)$ is indeed a non-negative integer. – Heisenberg Nov 5 '12 at 15:53
@Heisenberg: You should add that to the question; people shouldn't have to read comments under answers to understand the question. – joriki Nov 5 '12 at 15:56
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.