# Prove that D is strongly connected if and only if for every edge-cut S of the underlying graph G that separates V (G − S) into two sets A and B

I'm struggling with writing a detailed proof for this.

Let D be a digraph with at least two nodes, and let G be the underlying graph of D.

An edge-cut of G is a set S of edges of G such that G−S is disconnected, where G−S denotes the graph obtained from G by deleting all edges in S. Now,

Prove that D is strongly connected if and only if for every edge-cut S of the underlying graph G of D that separates V (G − S) into two sets A and B, there is an arc in D directed from a node in A to a node in B and an arc in D directed from a node in B to a node in A.

So far, i have assumed D is strongly connected. Taken u and v as two vertices in D, and since D is strongly connected both vertices are reachable from one another (path from u to v and a path from v to u).

Then an edge cut is performed on G, such that v and u are separated into two connected components, then v $$\in$$ A and u $$\in$$ B. I know that the edges that are cut represent the path from u to v and from v to u, but don't know how to explain via a proof. Also how do i explain the only if part?

For the forward part: Let $$D$$ be strongly connected connected, and let $$S\subseteq E(G)$$ be a cut inducing the components with vertex sets $$A$$ and $$B$$. Moreover, let $$v\in A$$ and $$u\in B$$. Since $$D$$ is strongly connected, there exists a directed path $$P_{vu}$$ from $$v$$ to $$u$$. Since $$u$$ and $$v$$ are in different components of $$G-S$$, $$P_{uv}$$ contains an edge in $$S$$. The argument is identical for proving there is an arc from $$B$$ to $$A$$. Since $$S$$, $$a$$ and $$b$$ were arbitrary, we are done.
Suppose now that for every edge-cut $$S$$ of $$G$$ of that separates $$V (G − S)$$ into two sets $$A$$ and $$B$$, there is an arc in $$D$$ directed from a node in $$A$$ to a node in $$B$$ and an arc in $$D$$ directed from a node in $$B$$ to a node in $$A$$. Consider any two vertices $$u$$ and $$v$$. We proceed by constructing a directed path from $$v$$ to $$u$$. Let $$A_1 :=\{v\}$$ and let $$S_1$$ be the set of outgoing edges from $$v$$, and let $$B_1:= V(G)\setminus A_1$$. By assumption, there is an edge $$e=vv_1$$ outgoing from $$v$$ to a vertex in $$B_1$$. If $$v_1=u$$ we are done, by adding $$u$$ to $$A_1$$ forming $$A_2$$, where $$A_2$$ contains a path from $$v$$ to $$u$$. Otherwise, iterate this process of adding vertices from $$B_1$$ to $$A_1$$ forming $$A_2$$ and $$B_2$$ and so on. By assumption, this can always be done, and eventually this iterative process stops when $$v$$ is added to $$A_i$$. At each step of this iteration, we only consider adding vertices which have an incoming edge from a vertex in $$A_i$$. Thus, there is a path from $$v$$ to the vertex added at step $$i$$. Thus, there is a path from $$v$$ to $$u$$.