Minimal edge cut

Question

Suppose that $C$ is a minimal edge cut of a graph $G=(V,E)$ is it possible that the removal of $C$ can split $G$ into three components? I ask this because i'm reading a proof which states that it's possible however it seems rather counter intuative as it seems any such edge edge cut shouldn't be minimal?

One thing i tried is looking at the following graph vertices $a,b$ and $c$ with an edge from $a$ to $c$ and from $b$ to $c$ then the two edges form an edge cut which split the graph into three components (in this case three independent vertices) however it is not a minimal edge cut.

Answer 1

As I understand it, a minimal cut set is one where no subset is also a cut set. If that's the case then I don't see how you can have three components connected by a minimal set. Here's my reasoning.

First, connect the three components with two edges. Then you can delete either edge and get a pair of components.

Now, connect them with three or more (N) edges. Now, you can choose a subset of (N - 1) edges such that one of the components is disconnected.

I tried drawing various convoluted graphs with chiral C3 symmetry, but none quite worked. This was the best I could do:

where the red edges are my attempt at a minimal cut set. You can see that you could delete four of them and disconnect one of the squares.

Answer 2

It sounds like you're right !

Suppose that $C$ is a minimal edge cut that yields at least 3 components. Call $G'$ the graph obtained after removing $C$ from $G$.

Put back any edge $e \in C$ in $G'$. The two endpoints of $e$ belong to at most 2 of the components, so adding $e$ can only reduce the number of components of $G'$ by one. In other words, $G' + e$ is still disconnected, which implies that $C$ wasn't minimal after all.