Is there something wrong with VertexConnectivity

Note: this is fixed in version 10.

As I noticed in the documentation VertexConnectivity is defined as the following

The vertex connectivity of a graph $g$ is the smallest number of vertices whose deletion from $g$ disconnects $g$.

Now for a CycleGraph I expect one needs to delete at least two vertices to make the resulting graph disconnected. Please correct me if I am driven by a wrong intuition here.

opt = {VertexLabels -> "Name", ImagePadding -> 10};
graph1 = CycleGraph[8, opt];
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}],opt];
Row[{graph1, graph2}]


Strange!

Now Mathematica is returning this not so intuitive values for the graph1 and graph2.

VertexConnectivity /@ {graph1, graph2}


{1,1}

How can one make any of these above graphs disconnected by deleting just one vertex? Can someone shade some light on this issue? EdgeConnectivity though gives understandable output for both the graphs.

• I think this is clearly a bug. Can you please report it? This would surely bite me too sooner or later. The graph-related functions seem to have more bugs than usual. Mar 28, 2013 at 14:57
• @Szabolcs I feared the same! This type of bugs can really make the overall graph functionality very much unstable and unreliable in nature. I will wait a bit as some WRI guys are active here as well...they may comment meanwhile... Mar 28, 2013 at 15:03
• << Combinatorica; graph1 = Cycle[8, Type -> Undirected]; VertexConnectivity @graph1 always worked :D Mar 28, 2013 at 21:02
• @belisarius Unfortunately Combinatorica is not too speedy because it's implemented purely in Mathematica. Apr 21, 2013 at 2:06

This was confirmed by support to be a bug.

One workaround is to use CombinatoricaVertexConnectivity:

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"] ] CombinatoricaVertexConnectivity@ GraphUtilitiesToCombinatoricaGraph[#] & /@ {graph1, graph2}  See here for the purpose of Block around Needs. P.S. It turns out that the GraphUtilitiesToCombinatoricaGraph 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"]].

EDIT

An easier way is using this package. Tutorial here.

IGraph["vertex.connectivity"][CycleGraph[5]]

(* ==> {.2} *)


Old version

As a workaround, you can access igraph through RLink. Once igraph is installed (install.packages(igraph)) and loaded (library(igraph)), do this:

vertexConnectivity[g_?GraphQ] :=
Round@First@RFunction["function (e) {
g <- graph.edgelist(e,directed=F);
vertex.connectivity(g)
}
"][List @@@ EdgeList[g]]

vertexConnectivity[CycleGraph[8]]

(* ==> 2 *)
`