# FindEdgeCut with weighted graphs

If I want to find a minimum cut between two nodes in a weighted graph, I would use FindEdgeCut as follows:

g = Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3, 1 \[UndirectedEdge] 3,
3 \[UndirectedEdge] 4}, EdgeWeight -> {2, 3, 5, 123}];
FindEdgeCut[g,1,4]


This function, however, returns the edge 3-4, so obviously the edge weights have not been considered.

I can find the minimum cut by using the maximum flow and so on, but I was wondering whether this error is more easily fixable or maybe it's just me and I don't see the error.

"so obviously the edge weights have not been considered"

The edge weights have been considered. It can be seen from careful reading the Details section of documentation on FindEdgeCut and comparing different examples. So what does FindEdgeCut do?

• An edge cut of a graph g is a set of edges whose deletion from g disconnects g.
• For weighted graphs, FindEdgeCut gives an edge cut with the smallest sum of edge weights.

Now if you compare this

Graph[{1 <-> 2, 2 <-> 3, 1 <-> 3, 3 <-> 4}, EdgeWeight -> {2, 3, 5, 123}] // FindEdgeCut


{1 <-> 2, 2 <-> 3}

with this

Graph[{1 <-> 2, 2 <-> 3, 1 <-> 3, 3 <-> 4}, EdgeWeight -> {2, 3, 5, 1}] // FindEdgeCut


{3 <-> 4}

you will understand how the EdgeWeight is taken account.

• Then maybe this is a version issue, I am using Mathematica 9.0.0.0 and while your second example does work, the first one does not. Also, I noticed a slight error in my question. What I actually wanted to do was FindEdgeCut[g,1,4], if that changes anything. – Thomas Sep 9 '13 at 8:35
• @Thomas 1,4 wouldn't change anything for this specific graph. I recommend contacting Wolfram Support for version issue. – Vitaliy Kaurov Sep 9 '13 at 8:46
• Just wanted to note that FindEdgeCut is totally unreliable with weights, even in 12.1 ... it's simply not safe to use because it's impossible to decide if it will return a correct result. It's one of those long-standing Graph bugs I keep complaining about. – Szabolcs Apr 3 at 11:19