# How can I find the vertex connectivity of a random graph? [duplicate]

I want to know the vertex connectivity of a random graph on (say) 4 vertices. I can get the vertex connectivity of each of the 11 graphs on 4 vertices with this:

Table[GraphData[{4, k}, "VertexConnectivity"], {k, 1, 11}]


If we label these 11 graphs we have 64 labeled graphs. In particular, the two unlabeled graphs with connectivity 2 have 3 + 6 = 9 labelings. I was expecting the vertex connectivity of 2 to appear with probability 9/64 in:

Table[VertexConnectivity[RandomGraph[BernoulliGraphDistribution[4, 0.5]]], {1000}]


However, I do not obtain this probability form the above calculation. I am using Mathematica 9.0.

• Is this a math question or a Mathematica one? You seem to have the answer to the question in the title. Are you asking why you don't get 9/64? It seems to me that you are getting ratios close 9/64. So what is the question then? – Szabolcs Oct 11 '16 at 9:56
• If you have v9, be aware that VertexConnectivity is buggy. mathematica.stackexchange.com/q/22261/12 – Szabolcs Oct 11 '16 at 10:54
• I AM using version 9. I am NOT getting ratios that are close to 9/64. In fact, I am not getting any 2's at all from the above code. Are you saying version 9 does not work correctly? – Geoffrey Critzer Oct 11 '16 at 14:56
• See the link from my comment, the details (which I don't all remember) are in there. All I remember is that sometimes VertexConnectivity would return incorrect answers in v9. This is fixed in v10.0+. – Szabolcs Oct 11 '16 at 15:00
• In version 11.0, Count[Table[ VertexConnectivity[ RandomGraph[BernoulliGraphDistribution[4, 0.5]]], {10000}], 2]/10000. returned 0.14. In v9 I get 0. v9 is definitely buggy. – Szabolcs Oct 11 '16 at 18:47