10
$\begingroup$

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]

Mathematica returns about 250000. I was expecting about half a million.

$\endgroup$
18
$\begingroup$

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
  ], 
  TableHeadings -> {None, {"Graph", "HamiltonianGraphQ"}}
]

Mathematica graphics

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:

Mathematica graphics

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]

Mathematica graphics

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]

Mathematica graphics

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.