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$
0

1 Answer 1

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$
4
  • 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, 2016 at 17:18
  • 1
    $\begingroup$ @Szabolcs That's in short what I'm saying above, right? $\endgroup$ Nov 12, 2016 at 17:20
  • 2
    $\begingroup$ Yes, I just gave you the technical term. $\endgroup$
    – Szabolcs
    Nov 12, 2016 at 17:21
  • $\begingroup$ @Szabolcs Thanks, for a moment I wasn't entirely sure whether it was an addition or a correction. $\endgroup$ Nov 12, 2016 at 18:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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