# A graph is strongly connected iff every non-trivial cut contains an edge

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)

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

• 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 Dec 25, 2022 at 17:26
• 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. Dec 25, 2022 at 17:27
• 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 Dec 26, 2022 at 8:12
• By definition, edges in $\delta(S)$ are from a vertex in $S$ to a vertex not in $S$, so that situation is not possible. Dec 26, 2022 at 11:49

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.

• 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. Dec 26, 2022 at 10:00
• Yes, $\delta(S)$ is the set of outgoing edges, i.e. going from a vertex inside $S$ to a vertex outside of $S$. Dec 26, 2022 at 11:11