Proving the correctness of an algorithm, which computes the connectivity of a directed graph Let $G=(V,E)$ be a directed graph. The connectivity of a graph is the defined as the cardinality of a smallest separator of $G$. A separator of $G$ is a subset $U$ of $V$, such that $G-U$ is not strongly connected.

Why does the following algorithm compute the connectivity of a graph correctly?

\begin{equation}
\begin{split}
&amp;\text{Connectivity}(\text{graph }G=(V,E)) \\
&amp;\;\;\;\;01\text{:}\;\;k=\infty \\
&amp;\;\;\;\;02\text{:}\;\;\text{for }i=1,\ldots,|V| \\
&amp;\;\;\;\;03\text{:}\;\;\{\\
&amp;\;\;\;\;04\text{:}\;\;\;\;\;\;\text{for each }v\in V\\
&amp;\;\;\;\;05\text{:}\;\;\;\;\;\;\{\\
&amp;\;\;\;\;06\text{:}\;\;\;\;\;\;\;\;\;\;\text{compute a minimum }v_i,v\text{-seperator }U_{v_i,v}\\
&amp;\;\;\;\;07\text{:}\;\;\;\;\;\;\;\;\;\;k=\min\left\{k,\left|U_{v_i,v}\right|\right\}\\
&amp;\;\;\;\;08\text{:}\;\;\;\;\;\;\;\;\;\;\text{if }(i&gt;k+1) \text{ return }k\\
&amp;\;\;\;\;09\text{:}\;\;\\
&amp;\;\;\;\;10\text{:}\;\;\;\;\;\;\;\;\;\;\text{compute a minimum }v,v_i\text{-seperator }U_{v,v_i}\\
&amp;\;\;\;\;11\text{:}\;\;\;\;\;\;\;\;\;\;k=\min\left\{k,\left|U_{v,v_i}\right|\right\}\\
&amp;\;\;\;\;12\text{:}\;\;\;\;\;\;\;\;\;\;\text{if }(i&gt;k+1) \text{ return }k\\
&amp;\;\;\;\;13\text{:}\;\;\;\;\;\;\}\\
&amp;\;\;\;\;14\text{:}\;\;\}
\end{split}
\end{equation}

More precisely, why can we return $k$ in line 08 (resp. 12) without concerning the other $u,v$-seperators?
Suppose that the algorithm is incorrect. We can slightly modify the algorithm by moving lines 8,12 just after the inner loop. If the algorithm returns $k$ incorrectly at the end of step $i$, then there must exist vertices $v_s,v_t$, for $s,t&gt;i$, and a set $S$ of size $k-1$ not containing $v_s,v_t$, such that after removing $S$ there is no path from $v_s$ to $v_t$. I claim that $v_1,\ldots,v_i \in S$: if $v_j \notin S$ for some $j \leq i$, then since $S$ does not disconnect $v_j$ from any other vertex, we would have a path $v_s \to v_j \to v_t$. Since $v_1,\ldots,v_i \in S$, in particular $|S| \geq i$. Stated differently, $k-1 \geq i$. So if $i &gt; k-1$, this is impossible.

My proof, if correct, shows that you can actually use the weaker condition $i &gt; k-1$ in lines 8,12.