I'm studying "Graph Theory" by Bondy and Murty, and I'm stuck with this exercise.
First, for a directed graph $D$, we define $\partial(X)$ ($X \subset V(D)$) to be the set of arcs whose ends are respectively in $X$ and $V(D) \setminus X$. We call $\partial(X)$ as a bond if none of any nonempty proper subset of $\partial(X)$ is equal to $\partial(Y)$ for some $Y \subset V(D)$.
Also, if a bond $\partial(X)$ is only comprised of arcs with tail in $X$ and head in $V(D) \setminus X$, we call $\partial(X)$ to be a directed bond.
Now here is the question:
Prove that a digraph is acyclic if and only if every bond is a directed bond.
I already proved the only if part, which is a trivial conclusion of the following claim that I already proved; an arc of a digraph is contained either in a directed cycle or in a directed bond, but not both. But I am stuck with the if part; the claim tells that every arc should be contained in some directed bond, but it does not tell that every bond should be a directed bond.
Any help would be greatly appreciated.
Let us assume that $G$ is connected; i.e., the empty set of arcs do not form a bond. If $G$ has a directed cycle then it has a bond that is not directed. If we can show this then we will show the "if" direction.
Let $C$ be a directed cycle and let $x$ and one vertex and $y$ another vertex in $C$, and $F$ a minimum-sized edge cut that satisfies the condition that $x$ is in one part of $G \setminus F$ and $y$ another part. Then $F$ is a bond; if an edge is taken away from $F$ then the resulting set of edges is not a cut. [Indeed, let $X$ be the component of $G \setminus F$ containing $x$ and $Y$ the component of $G \setminus F$ containing $Y$. Then each edge in $F$ is between $X$ and $Y$. [Indeed, let $e$ be an edge in $F$ with one endpoint in $X$ and the other in another component $Z \not = Y$. Then $F \setminus \{e\}$ is still such that $x$ is in one part of $G \setminus (F \setminus \{e\})$ and $y$ another part, contradicting the assumption that $F$ is a minimum-sized edge cut. Likewise if $e$ had both endpoints in neither $X$ nor $Y$ or both endpoints in $X$ or both endpoints in $Y$. Thus indeed, each edge in $F$ is between $X$ and $Y$.] Furthermore, $G \setminus F$ has only those two components $X$ and $Y$ lest $G$ is not connected. As $G \setminus F$ has only two components and every edge in $F$ is between $X$ and $Y$ it follows that $F$ is a minimal bond adding an edge back from $F$ would connect $X$ and $Y$.]
However, as $x$ and $y$ are in a cycle, there is in $G$ a path $P_{xy}$ directed from $x$ to $y$ and there is in $G$ a path $P_{yx}$ directed from $y$ to $x$. Write $P_{xy} = xu_1u_2\ldots y$ and $P_{yx} = yv_1v_2\ldots x$. Then for some $i$ and $j$, the bond $F$ must contain both the arcs $u_iu_{i+1}$ and $v_jv_{j+1}$ where $y,v_1,\ldots, v_j$ is in $Y$ and $x,u_1, \ldots, u_i$ is in $X$. [writing $x=u_0$ and $y=v_0$ and $y=u_l$ and $x=v_m$ where $l$ and $m$ are positive integers such that $P_{xy}$ has $l+1$ vertices and $P_{yx}$ has $m+1$ vertices] So $F$ is not directed.
As for the other direction: The "only if": Let $G$ be a digraph on 3 vertices $a$, $b$, and $c$ consisting of the arcs $ab$, $ac$, and $bc$. Then $G$ is a DAG. However, the set of arcs $\{ ab, bc \}$ form a bond between $X =\{b\}$ and $Y =\{a,c\}$, and is not a directed bond, as one arc $bc$ has its head in $X$ and the other $ab$ its tail in $X$. So even though $G$ is a DAG, not every bond is a directed bond. So the "only if" does not hold.