How would I find the minimum non-trivial cut in a graph? I know that there is an algorithm which computes the minimum cut in a graph $G$.
I have a situation where I am trying to compute the minimum non-trivial cut of $G$, where I say that a cut is trivial if one of the sides has only one vertex. In other words, I don't want to consider cuts which are merely the set of edges exiting a single vertex.
What is the best algorithm for this problem?
 A: Here is a starting point that makes $O(n^2)$ calls to a max-flow subroutine:

*

*Let $\{v,w\}$ be an arbitrary pair of vertices in $G$. Iterate over pairs of vertices $\{x,y\}$ disjoint from $\{v,w\}$. (If you want both sides of your cut to be connected, then limit $\{v,w\}$ and $\{x,y\}$ to adjacent pairs of vertices.)

*For each case of $\{v,w\}$ and $\{x,y\}$, let $H$ be the graph obtained by contracting $\{v,w\}$ to a single vertex $s$, and contracting $\{x,y\}$ to a single vertex $t$. (We allow double edges out of $s$ and $t$ when $v,w$ or $x,y$ have a common neighbor.) Find a minimum $s,t$-edge cut in $H$.

*If there is a minimum nontrivial cut in which $v$ and $w$ are on the same side, one of the cases above will find it. So it remains to consider the case where $v$ and $w$ are on opposite sides.

*For this, iterate over pairs $\{x,y\}$ disjoint from $\{v,w\}$ again, but define $H$ by contracting the pairs $\{v,x\}$ and $\{w,y\}$ instead; otherwise, do exactly what we did in step 2.

Compare this to an algorithm that finds a minimum cut with $O(n)$ calls to a max-flow subroutine, by fixing a vertex $v$ and looking for cuts that separate $v$ from each possible vertex $w$. (That's not the best algorithm out there, but it is pretty good.)
