1
$\begingroup$

As the title states, I am asked to prove that a directed graph $G=(V,E)$ is strongly connected iff for all non-empty subsets $\emptyset \neq S \subset V$, the cut $\delta(S) \neq\emptyset$, where $$\delta(S)= \left\{ (u,v)\in E \mid u \in S,\; v\in V \setminus S \right\}.$$

I've shown that if $G$ is strongly connected, there has to be atleast 1 (possibly 2) edges in $\delta(S)$ for any $\emptyset \neq S\subset V$ which is one side of the proof.

However, when approaching the other side, I cant seem to find any intuition on how to start the proof, I just cant seem to understand what information I can deduce from the fact that there are edges which cross every non-trivial cut (basically the same as saying that $\delta (S)\neq\emptyset $ for all $\emptyset\neq S\subset V$)

(I've proven the first direction by showing that since $S$ is not empty and $G$ is strongly connected, there has to be an edge from a vertex which is not in $S$ to a vertex in $S$, thus showing that $\delta(S)$ is not empty)

$\endgroup$

2 Answers 2

2
$\begingroup$

You can prove the existence of a path between any $u$ and $v$ vertices using the following process:

  • set $S = \{u\}$;
  • while $S \neq V$ do
    • for each $(x, y)\in \delta(S)$, add $y$ to $S$

The property "all vertices in $S$ are reachable from $u$" is a loop invariant for the while loop.

If you suppose that $\delta(S)\neq \emptyset$ for all non-trivial $S$, that means that the size of $S$ increases each loop, and the loop halts if and only if $S = V$.

$\endgroup$
4
  • $\begingroup$ Can you elaborate about the invariant? I can’t seem to understand how it leads to the graph being strongly connected, once the loop ends $\endgroup$
    – Aishgadol
    Dec 25, 2022 at 17:26
  • $\begingroup$ It shows that all vertices of $V$ are reachable from $u$. Do it for any vertex $u\in V$, and you would have proven that the graph is strongly connected. $\endgroup$
    – Nathaniel
    Dec 25, 2022 at 17:27
  • $\begingroup$ What bothers me is that there could be a 'situation' where we start with some $u\in V$ s.t. $S=\{ u \}$ but eventually, reach a state where the edges in $\delta (S)$ are only directing into $S$, which means we dont have a vertex we could add to $S$ which is reachable from a vertex $u \in S$ and then we're basically stuck, not being able to show the graph is strongly connected $\endgroup$
    – Aishgadol
    Dec 26, 2022 at 8:12
  • $\begingroup$ By definition, edges in $\delta(S)$ are from a vertex in $S$ to a vertex not in $S$, so that situation is not possible. $\endgroup$
    – Nathaniel
    Dec 26, 2022 at 11:49
0
$\begingroup$

For the sake of a contradiction, assume the graph is not strongly connected. If a graph is not strongly connected, then there is a pair $u$ and $v$ such that there is no path from $u$ to $v$.

Let $R(u)$ be the reachability set of $u$, i.e. the vertices reachable from $u$.

Now, since $v \notin R(u)$, it means that $S = R(u) \subset V$ with $\delta(S) = \emptyset$ contradicting the assumption that every non-trivial cut is nonempty.

Our only assumption was that the graph was not strongly connected which then must be false. The graph is strongly connected.

$\endgroup$
2
  • $\begingroup$ Thank you for your explanation, I seem to have missed a massive information piece which states that all edges in $\delta (S)$ are directed from $S$ to $V/S$, and since (as you've mentioned) $\delta (S) \neq \emptyset$ , there's always an edge of which we can add the end-point vertex into $S$, and keep $S$ strongly connected. $\endgroup$
    – Aishgadol
    Dec 26, 2022 at 10:00
  • 1
    $\begingroup$ Yes, $\delta(S)$ is the set of outgoing edges, i.e. going from a vertex inside $S$ to a vertex outside of $S$. $\endgroup$
    – Pål GD
    Dec 26, 2022 at 11:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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