1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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