Htykuut

I would like to know what you think of the following statement and, in case it is true, how would you prove it. Consider a directed graph $G=(V,A)$ where every vertex has degree higher or equal than three, and which contains an r-arborescence (a directed spanning tree); then

the graph has a directed cycle iff for every maximal obstruction-free family of cuts $mathcal{S}={S_i}_{i=1}^{|V|}$ such that $S_isubset S_{i+1}$, $exists tilde Sinmathcal{S}$ with $|delta^-(tilde S)|geq 1$ and $|delta^+(tilde S)|geq 1$.

An obstruction-free family of cuts is here defined as a family such that $forall Sinmathcal{S}$, no subset of $mathcal{S}setminus S$ forms a partition of $S$. Furthermore, $delta^+(S)$ is the set of outgoing edges in the boundary of $S$ and $delta^-(S)$ is the set of incoming edges in the boundary of $S$.

If my reasoning are right then it took me more time to understand the statement than to prove it. :-) As I understood, the condition after “iff” is equivalent to that for any ordering $v_1,dots, v_n$ of vertices of there exists $i$ such that $G$ contains edges $(v_j,v_{j’})$ and $(v_{k’},v_k)$ with $j,kle i<j’,k’$. Now we can prove the statement for any directed graph $G$.

Assume that the graph $G$ has a directed cycle $C$. Then given an ordering of vertices of $G$ let $v_i$ be the first vertex of $C$ with respect to this order. Then the condition holds even for $j=k=i$.

Conversely, if $G$ is a directed acyclic graph then a topological ordering of its vertices clearly violates the condition.