# Question:How can one determine whether a given set of edges is an edge cut of a graph?

## Question:How can one determine whether a given set of edges is an edge cut of a graph?

Maple

I previously asked the following question, and a primes member dharr  provided a perfect answer. The question I asked today is slightly different.

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 graph K3,3, a set of any seven edges of K3,3 is an edge separator, but a set of any seven edges of K3,3 is not an edge cut.

It is easy to determine whether a set of edges is an edge separator.

```with(GraphTheory):
with(combinat):
G:=CompleteGraph(3,3);
edge:=choose(Edges(G), 7):
seq(nops(ConnectedComponents(DeleteEdge(G,s,inplace= false))),s in edge)
```

4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4

For another exmaple,

In  the left  figure,  the brown edges highlighted represent an edge-separating set, but it is not an edge cut. The set of brown edges on the right is an edge cut.

But how to 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.

﻿