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

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 .

 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

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

• If we take three instances of complete graph $K_r$ and connect them in pairs by three edges $S=\{e_1,e_2,e_3\}$. We obtain a connected graph $G$. The graph $G-S$ consists of three connected components. Is this not a counterexample for $k=r$? Jan 19 at 14:20
• Now is $S$ a minimum $r$-restricted-edge-cut? ($\{e_1,e_2\}$ is an $r$-restricted-edge-cut with fewer edges than $S$.) I hope I understand correctly. Jan 19 at 14:30
• I agree with you. Indeed, if $S$ is minimal cut and $u\in S$, then graph $H=G-S+u$ is still connected, but then graph $H-u=G-S$ has exactly two connected components. Right? Jan 19 at 15:30
• Yes. A minimal edge cut set is an edge cut where no subset is also a cut set. In fact, I was just asking if a minimum $k$-restricted-edge-cut is always a minimal cut. (Note that there is a difference between the meaning of "minimum" and "minimal".) Jan 19 at 15:41
• It is not very clear how a minimum cut can be a non-minimal cut. Jan 19 at 16:05

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

• Thank you very much. I got the theorem involving bonds mixed up by mistake. (Bondy text, 2008, Theorem, 2.15 (P62)) In a connected graph $G$, a nonempty edge cut $∂(X)$ is a bond if and only if both $G[X]$and $G[V\setminus X]$ are connected. The definition of edge cuts in Bondy book there is a little different. Jan 22 at 5:43