I'm trying to use Mathematica to compute the minimal vertex cut for graphs. From what I understood, VertexConnectivity of a graph should correspond to the number of vertices in the minimal vertex cut.

However, when I use Mathematica 9.0 on a graph, I get a VertexConnectivity of 1, but the minimal cut computed by Mathematica has 33.

This seems strange! Is this a bug, or am I missing something? Any help would be appreciated!

Here's a link to the text used to generate the graph which I am testing: http://pastebin.com/WWk0Gk8G VertexConnectivity and FindVertexCut are the functions I'm using.

Regards, Dave

  • $\begingroup$ Welcome to Mathematica.SE! I suggest the following: 1) As you receive help, try to give it too, by answering questions in your area of expertise. 2) Read the faq! 3) When you see good questions and answers, vote them up by clicking the gray triangles, because the credibility of the system is based on the reputation gained by users sharing their knowledge. Also, please remember to accept the answer, if any, that solves your problem, by clicking the checkmark sign! $\endgroup$ – user9660 Dec 7 '14 at 16:36
  • 1
    $\begingroup$ VertexConnectivity is buggy in v9, unfortunately. The correct answer is 33, not 1. I marked as a duplicate of the thread discussing this. You can either upgrade to v10 (which has this fixed) or use igraph as a workaround (as described in the link). $\endgroup$ – Szabolcs Dec 7 '14 at 16:42
  • $\begingroup$ Thanks for the help! Strange that such a bug managed to get through. $\endgroup$ – Dave Dec 9 '14 at 12:29

You may see that removing a single vertex doesn't disconnects your graph. It's a bug,as noted in the comments:

And @@ Thread[ Length /@  ConnectedComponents /@ (VertexDelete[g, #] & /@ VertexList@g) == 1]

(*  True *)

Not the answer you're looking for? Browse other questions tagged or ask your own question.