# 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. – Szabolcs Mar 28 '13 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... – PlatoManiac Mar 28 '13 at 15:03
• << Combinatorica; graph1 = Cycle[8, Type -> Undirected]; VertexConnectivity @graph1 always worked :D – Dr. belisarius Mar 28 '13 at 21:02
• @belisarius Unfortunately Combinatorica is not too speedy because it's implemented purely in Mathematica. – Szabolcs Apr 21 '13 at 2:06

This was confirmed by support to be a bug.

One workaround is to use CombinatoricaVertexConnectivity:

graph1 = CycleGraph;
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]

(* ==> {.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]

(* ==> 2 *)
`