This was confirmed by support to be a bug. --- One workaround is to use ``Combinatorica`VertexConnectivity``: graph1 = CycleGraph[8]; graph2 = UndirectedGraph[ Graph[{1 -> 3, 1 -> 7, 1 -> 10, 2 -> 5, 2 -> 6, 3 -> 6, 3 -> 10, 4 -> 7, 4 -> 8, 4 -> 9, 5 -> 9, 6 -> 10, 7 -> 8, 8 -> 9}]]; Block[{$ContextPath}, Needs["Combinatorica`"]; Needs["GraphUtilities`"] ] Combinatorica`VertexConnectivity@ GraphUtilities`ToCombinatoricaGraph[#] & /@ {graph1, graph2} See [here][1] for the purpose of `Block` around `Needs`. ---- P.S. It turns out that the ``GraphUtilities`ToCombinatoricaGraph`` function re-adds Combinatorica to the context path every time it's called. If you prefer not to have Combinatorica in the context path, you can consider editing GraphUtilities.m and changing ``Needs["Combinatorica`"]`` to ``Block[{$ContextPath}, Needs["Combinatorica`"]]``. [1]: http://mathematica.stackexchange.com/q/5563/12