# Finding the minimum vertex cut of a graph

Bug introduced in 9.0.1 or earlier and fixed in 10.2.0
Note: FindVertexCut is new in 9.0.

It seems that Mathematica is not correctly finding the smallest set of vertices that will disconnect a graph. Here is an example:

 g = GraphData[{"Cycle", 5}]
FindVertexCut[g];
HighlightGraph[g, %]


results in vertices {3, 4} being removed. But removing two adjacent vertices of a cycle doesn't increase the number of components. If we remove 3 and 4, the graph is a tree and is still connected. This ends up happening with quite a few graphs, another example being the complete graph with 6 vertices. It only removes one vertex and doing so will obviously not disconnect the complete-6 graph. But it does work some of the time; e.g., with a 6-cycle, Mathematica removes two non-adjacent vertices.

Have I used FindVertexCut incorrectly? FindVertexCut with only a graph as its argument will result in "the smallest vertex cut of" my graph, and according to documentation, "A vertex cut of a graph g is a list of vertices whose deletion from g disconnects g." What's the problem here?

• Seems like a bug ... Works OK. for n > 5 Oct 22, 2014 at 12:26
• Your conjecture appears to only be true for cycles. From what I can see, it never works on complete graphs (except for n = 2 or n = 3). Oct 22, 2014 at 12:35
• Yup. I was talking about cycles. You're right about complete graphs too. Oct 22, 2014 at 12:37
• Other users: Please confirm and tag as bugs if you can repro Oct 22, 2014 at 12:39

This is bugged still in 10.1.

If you are forced to live with the buggy function, here's a brute-force method that should work correctly: it checks the size of a minimum cut, and tries all subsets of vertices of that size. Below, I assume that VertexConnectivity still works correctly.

g = CycleGraph[5, VertexLabels -> "Name"]

DisconnectedGraphQ[g_] := ! ConnectedGraphQ[g];
gh = VertexDelete[g, #] & /@ Subsets[VertexList[g], {VertexConnectivity[g]}];
cut = SelectFirst[gh, DisconnectedGraphQ, {}];
If[SameQ[{}, cut], VertexList[g], Complement[VertexList[g], VertexList[%]]]


Furthermore, the overloaded version FindVertexCut[g,s,t] is bugged. Consider the following:

g = Graph[{1 <-> 2, 1 <-> 3, 1 <-> 4, 1 <-> 5, 2 <-> 3, 2 <-> 4,
2 <-> 5, 3 <-> 4, 3 <-> 5, 4 <-> 5, 1 <-> 8, 8 <-> 3},
VertexLabels -> "Name"];
HighlightGraph[g, FindVertexCut[g, 5, 8]]
Length[ConnectedComponents[VertexDelete[g, FindVertexCut[g, 5, 8]]]]


Here, removing the claimed vertex cut {1} does not increase the number of components, and is not a vertex separator for vertices 5 and 8.

Update: Now I recommend using IGraph/M instead:

<<IGraphM

IGMinSeparators[g]
(* {{2, 5}, {2, 4}, {3, 5}, {1, 3}, {1, 4}} *)


An alternative workaround is using igraph through my IGraphR package.

minimum.size.separators gives all possible smallest vertex cuts.

Example:

<< IGraphR

g = CycleGraph[5, VertexLabels -> "Name", VertexSize -> Large]

vcs = IGraph["minimum.size.separators"][g]
(* {{2., 5.}, {2., 4.}, {3., 5.}, {1., 3.}, {1., 4.}} *)

HighlightGraph[g, #] & /@ Round[vcs] • @mrm You can't compare them in general. There's of course an overhead to calling igraph, but igraph will sometimes use different algorithms which might make its performance significantly different. Apr 9, 2015 at 13:31
• Can you double check my claim for the st-version of FindVertexCut (see my update)? Thanks! :-)
– Juho
Apr 13, 2015 at 13:27
• @mrm Sorry, today is very busy here. Remind me in a few days if I don't respond. Apr 13, 2015 at 17:05