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

Question

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.

edgeSet = Subsets[EdgeList[g], {7}]; 
ConnectedGraphQ[EdgeDelete[g, #]] & /@ edgeSet

{False, False, False, False, False, False, False, False, False, \
False, False, False, False, False, False, False, False, False, False, \
False, False, False, False, False, False, False, False, False, False, \
False, False, False, False, False, False, False}

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.

Edits: Below is my inquiry on Computer Science Stack. I believe that the algorithm (that the member Highheath provided) is reliable.

• https://cs.stackexchange.com/questions/157731/how-to-determine-if-a-set-of-edges-is-an-edge-cut-of-a-graph

Answer 1

Assuming I've understood the answer from the CS stack exchange, I think this is relatively straightforward. Making use of your existing example, here is what we can do:

g = {1 <-> 2, 1 <-> 3, 2 <-> 3, 2 <-> 4, 3 <-> 4, 4 <-> 5, 5 <-> 6, 
 4 <-> 6, 6 <-> 7, 5 <-> 7, 7 <-> 8, 8 <-> 9, 7 <-> 9, 3 <-> 8};
e1 = {2 <-> 4, 3 <-> 4, 3 <-> 8, 6 <-> 7, 5 <-> 7};
e2 = {2 <-> 4, 3 <-> 4, 3 <-> 8};

So the edge set e1 should not be an edge cut (example on the left of your illustration), while the edge set e2 should be an edge cut (on the right). I'm working just with lists of edges, some of these operations will be slightly different if you are already using Graph for your graphs (e.g. Complement might be replaced with EdgeDelete).

If you want to be very thorough, the first thing to test might be that each of e1 and e2 is a subset of the graph g at all. (I often assume I will always give my code "good" input, but for the sake of allowing robust and potentially "bad" or "invalid" input, we could test this first.)

SubsetQ[g, e1]
SubsetQ[g, e2]
(* Out[] = True *)
(* Out[] = True *)

Technically, you also need to test that e1 and e2 are loop free. It seems like those are not allowed (although those might not be even permitted as input too, so this might be unnecessary). Note that it needs a graph object, not just a list of edges.

LoopFreeGraphQ[Graph[e1]]
LoopFreeGraphQ[Graph[e2]]
(* Out[] = True *)
(* Out[] = True *)

We can define the new graphs with these edges removed (output suppressed, but you can remove the semicolons to show it).

ge1 = Complement[g, e1];
ge2 = Complement[g, e2];

Then you can contract to those components as:

vc1 = VertexContract[g, ConnectedComponents[ge1]];
vc2 = VertexContract[g, ConnectedComponents[ge2]];

This will show you two graphs, $K_3$ and $K_2$ respectively, if you remove the semicolons that suppress output. One is bipartite, the other isn't, which is the key feature as noted over in the CS stack exchange.

BipartiteGraphQ[vc1]
BipartiteGraphQ[vc2]
(* Out[] = False *)
(* Out[] = True *)

Overall, you could pack that up into a single command.

edgecuttest[g_, e_] := SubsetQ[g, e] &&
 LoopFreeGraphQ[Graph[e]] &&
 BipartiteGraphQ[VertexContract[g, ConnectedComponents[Complement[g, e]]]]

Note that if you wanted to see the contraction with multi-edges, you can. I don't think it matters in terms of what you want this to eventually do, but the IGraphM package will help you do that. You can read about it here. To install it, you can run a command like this one:

Get["https://raw.githubusercontent.com/szhorvat/IGraphM/master/IGInstaller.m"]

Then load the package with:

<< IGraphM`

You can see the contractions with multi-edges with:

IGVertexContract[Graph[g], ConnectedComponents[ge1], MultiEdges -> True]
IGVertexContract[Graph[g], ConnectedComponents[ge2], MultiEdges -> True]

This shows the $K_3$ with two double-edges, and then the $K_2$ with triple edge, as in the original post on CS stack exchange. Note that the first argument requires Graph, unlike above with VertexContract.

Although it doesn't seem necessary, you could redo the single command version with this one as well:

edgecuttestIGM[g_, e_] := SubsetQ[g, e] &&
 LoopFreeGraphQ[Graph[e]] &&
 BipartiteGraphQ[ IGVertexContract[Graph[g], ConnectedComponents[Complement[g, e]]]]

If you are using a Graph object or other format as your input, rather than list of edges, and if you are not able to tweak these commands to produce the same output, please let me know and I can probably revise the answer by tinkering to get it to fit your input.