Is RandomGraph really random?

I think there are 2 non-Hamiltonian graphs with 5 vertices and exactly 7 edges. There are a total of 4 graphs with 5 vertices and 7 edges. If I run (in version 9):

n = 5;
Count[Table[HamiltonianGraphQ[
RandomGraph[{n, Binomial[n - 1, 2] + 1}]], {1000000}], False]


Indeed there are four graphs with 5 vertices and 7 edges, two of which have a Hamiltonian cycle:

TableForm[{#, HamiltonianGraphQ@#} & /@
DeleteDuplicates[
RandomGraph[{n, Binomial[n - 1, 2] + 1}, 1000],
IsomorphicGraphQ
],
]


However, RandomGraph doesn't sample from that space, but from a larger space that includes many graphs that are isomorphic to each other. If you examine some of the graphs they look identical but under the hood they are different:

Draw 10,000 random graphs and tally taking isomorphism into account and you get this:

Tally[RandomGraph[{n, Binomial[n - 1, 2] + 1}, 10000], IsomorphicGraphQ]


As you can see the graphs with a Hamiltonian cycle are not available in this set in the same amount as the graphs without such a cycle, hence your results.

In fact, there are a total of 120 different graphs with the 5,7 property:

RandomGraph[{n, Binomial[n - 1, 2] + 1}, 100000] // Union // Length


120

with isomorphicity distributed as follows:

Tally[RandomGraph[{n, Binomial[n - 1, 2] + 1}, 100000] // Union, IsomorphicGraphQ]


The non-Hamiltonions make up precisely 1/4 of the set. This is consistent with your results.

• It samples from the set of labelled graphs (vertices are considered distinguishable). Essentially, each entry in the adjacency matrix is an independent random variable. – Szabolcs Nov 12 '16 at 17:18
• @Szabolcs That's in short what I'm saying above, right? – Sjoerd C. de Vries Nov 12 '16 at 17:20
• Yes, I just gave you the technical term. – Szabolcs Nov 12 '16 at 17:21
• @Szabolcs Thanks, for a moment I wasn't entirely sure whether it was an addition or a correction. – Sjoerd C. de Vries Nov 12 '16 at 18:05