If $S$ is a minimum $k$- restricted-edge-cut of $G$, then must $G-S$ have exactly two connected components?

Question

An edge cut is a set of edges that, if removed from a connected graph, will disconnect the graph.

For a connected graph $G=(V ,E)$, an edge set $S ⊂ E$ is a $k$-restricted-edge-cut, if $G−S$ is disconnected and every connected component of $G−S$ has at least $k$ vertices.

We can see the concept of $k$- restricted-edge-cuts is one of generalizations of edge cuts. The restricted edge connectivity was proposed by Esfahanian and Hakimi in [1].

[1] Esfahanian A H, Hakimi S L. On computing a conditional edge-connectivity of a graph[J]. Information processing letters, 1988, 27(4): 195-199. doi.org/10.1016/0020-0190(88)90025-7

PS (Off-topic remarks): They give a polynomial algorithm for computing the $2$- restricted-edge-cut of graphs. But I feel that it may not be correct. I have been trying to implement this algorithm, but failed, see

• How-To-Compute-The-Restricted edge connectivity

For example, we have a graph as follows.

Then we can check that the edge set $\{(0,1),(0,2)\}$ is a minimum $2$-restricted-edge-cut of the above graph (we note that any cut edge $(0,4)$ or $(0,5)$ is not $2$-restricted-edge-cut).

A minimal edge cut set is an edge cut where no subset is also a cut set.

I know that the following claim holds.

• A edge cut $S$ is a minimal edge cut if and only if $G-S$ have exactly two connected components.

So a natural question is:

Question. If $S$ is a minimum (or minimal) $k$-restricted-edge-cut of $G$, then must $G-S$ have exactly two connected components?

I am looking for counterexamples (or prove it).

Answer 1

For brevity, use "CC" for "connected component".

A edge cut $S$ is a minimal edge cut if and only if $G-S$ have exactly two CCs.

While the "only if" direction is true, the "if" direction is wrong since $S$ may contain redundant edges. For example, consider a graph with vertices $a,b,c,d$ and edges $ab,bc,cd,db$. Edge cut $\{ab, bc\}$ is not minimal since $\{ab\}$ is an edge cut, too. Both edge sets "cut" the graph into two CCs.

---

If $S$ is a minimal $k$-restricted-edge-cut of $G$, then must $G−S$ have exactly two CCs?

Of course. Otherwise $G-S$ has at least three CCs. Since $G$ is connected, there is an edge $e$ in $G$ between two of those CCs. $e$ must be in $S$. Consider $S'=S-\{e\}$. Here are the CCs of $G-S'$:

• Every CC in $G-S$ other than those two CCs connected by $e$.
• the union of those two CCs in $G-S$ connected by $e$ together with $e$

So $G-S'$ has two CCs. That means $G-S'$ is disconnected. Each CC of $G-S'$ is either a CC of $G-S$ or the union of two CCs of $G-S$ together with $e$. Hence, $S'$ is also a $k$-restricted edge cut, which contradicts with the minimality of $S$.