# How to determine if a set of edges is an edge cut of a graph?

An edge cut of a graph $$G$$ induced by a partition of $$G$$'s vertices into sets $$X$$ and $$Y$$ is the set of all edges with one endpoint in $$X$$ and another endpoint in $$Y$$.

An edge separator is a set of edges whose removal will increase the number of connected components in the graph.

Note that these are two distinct concepts and cannot be considered equivalent.

An edge separator is not necessarily an edge cut. For example,

For the complete bipartite geaph $$K_{3,3}$$, a set of any seven edges of $$K_{3,3}$$ is an edge separator, but a set of any seven edges of $$K_{3,3}$$ is not an edge cut.

For another exmaple,

The brown edges highlighted in the above Figure represent an edge-separating set, but it is not an edge cut. The set of brown edges on the right is an edge cut.

It is easy to determine whether a set of edges is an edge separator. But how do we determine if a set of edges is an edge cut of a graph? I don't have a good idea yet, but I have a rough idea which is to color the set of vertex-ends of edges under consideration and then see if a partition as defined by the edge cut can be found.

As you say, a cut in a graph $$G=(V,E)$$ is an edge set $$C$$ with the property that you may partition the vertices of $$G$$ (let's call the parts $$A$$ and $$B$$) in such a way that $$C$$ is exactly the set of edges with one end in $$A$$ and the other in $$B$$. This implies that the subgraph $$H=(V,C)$$ is bipartite with color classes $$A$$ and $$B$$. However, it is not enough to check that $$H$$ is bipartite, as this may disregard vertices that should be on the same side.

A good trick to use in a situation like this is contraction, i.e. we shrink every component of $$\overline{H}=(V,E-C)$$ down to a single vertex and let the edges in $$C$$ go between these instead. A simple way to achieve this is to find all the components of $$\overline{H}$$ (just run your favorite search algorithm on the graph until all vertices are seen), and build a new graph $$\widetilde{H}$$ where:

• Each vertex corresponds to a component of $$\overline{H}$$
• Each edge corresponds to an edge in $$C$$, with the endpoints corresponding to the components of endpoints of the original edge
• Multiple edges and loops are allowed

Now, $$C$$ is a cut in $$G$$ if and only if $$\widetilde{H}$$ is bipartite and has no loops.

I made the graphs $$\widetilde{H}$$ corresponding to the graphs in your figure to make it a bit more clear:

You should be able to do all of this in $$O(|V|+|E|)$$ time.

• Why can't there be loops in $\widetilde{H}$ when $C$ is a cut? If one component of $G−C$ is a cut edge, won't it create a loop when contracted the component? Commented Feb 26, 2023 at 3:34
• Sorry, it seems that no new self-loop is created during the contraction process. Was the self-loop allowed in your graph $G$ itself? Commented Feb 26, 2023 at 8:03
• I'm sorry, I see the wording was a bit off there. A loop corresponds an edge that goes between two vertices in the same component in $G$. Strictly speaking, if one of the edges make a loop, then you instantly know that $C$ is not a cut, as it should only contain edges that run between different components of $G$. So it would maybe be better if I said that you disallow loops since if you encounter them you instantly know that you are dealing with a NO-instance. Commented Feb 26, 2023 at 8:25
• Thank you very much for your reply. The self-loops in the connected components of G-C were not mentioned to be handled (perhaps they can be simply deleted). Overall, the algorithm you provided is undoubtedly correct. Commented Feb 26, 2023 at 8:51