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
    Ah sorry about that. Yes, $\phi(e)$ is indeed a non-negative integer.2012-11-05
  • 0
    @Heisenberg: You should add that to the question; people shouldn't have to read comments under answers to understand the question.2012-11-05
  • 0
    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$.2012-11-05
  • 0
    @Heisenberg: I don't see where you added it. It only says that $\phi(e)\ge0$.2012-11-05
  • 0
    @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.2012-11-05
  • 0
    Why is there only one directed cycle? If $v_{1}, v_{2}, v_{3}$ are the vertices of the graph, then aren't $v_{1} -> v_{2} -> v_{3}$, $v_{2} -> v_{3} -> v_{1}$ and $v_{3} -> v_{2} -> v_{1}$ all directed cycles?2012-11-05
  • 0
    But thank you for the clarification!2012-11-05
  • 0
    @Heisenberg: I guess you could count those as distinct cycles, yes. I wouldn't, but as I said, distinctness isn't relevant here.2012-11-05
  • 0
    So I'm assuming it suffices to only show that there must exist a directed cycle, because we can choose a given cycle a certain amount of times (by non-uniqueness) to satisfy the equation?2012-11-05
  • 0
    @Heisenberg: I don't understand. Are you saying it's enough to show that there's at least one directed cycle in the graph? I don't see why that should suffice.2012-11-05
  • 0
    How about, showing that there must exist directed cycles and if an edge is not part of a directed cycle, then $\phi(e) = 0$?2012-11-05
  • 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