Selection of an n-vertex graph at random Let's say I want to select, at random, an $n$-vertex graph $G=(V,E)$ from the set of all $n$-vertex graphs.
One way to do this would be to take the empty graph on $n$ vertices and then add each potential edge $\{u,v\}$ with probability $0.5$. The problem with this approach, however, is that it does not consider graph isomorphisms. So, strictly speaking, this process is only randomly selecting (constructing) a member from the set of $n$-vertex graphs and their isomorphisms.
Programs like nauty, Maple and Sage have facilities for generating the complete set of non-isomrphic graphs on $n$ vertices. However, the growth rates of these sets in relation to $n$ are very steep.
Let's say, then, that I want to select a 100-vertex graph from the set of all non-isomorphic graphs on 100 vertices. Is there a way of doing this without first having to generate the complete set?
 A: There is a very efficient method.
See Nicholas C. Wormald Generating Random Unlabelled Graphs
A: Ok, so here's what I've found.
The aim of this thread has been to identify a method that generates an $n$-vertex unlabelled graph uniformly at random from the space of all such graphs. The 1987 paper of Wormald contains several methods for doing this, but understanding these methods requires a very thorough knowledge of group theory and related concepts. Also, I've not been able to find any subsequent information on how to implement these methods.
However, the good news is that the paper also contains a very simple method called Quick-Graph that should be sufficient for most purposes. It operates as follows:

*

*Produce a random (Erdős–Rényi) graph $G_{n,0.5}$. That is, take the empty graph on $n$ vertices and add each potential edge $\{u,v\}$ with probability $0.5$.

*Remove the vertex labels from this graph. Now, with probability $p=2^{n-1}/(3n^2+2^{n-1})$, this graph is an $n$-vertex unlabelled graph that has been selected uniformly at random from the space of all unlabelled $n$-vertex graphs. Else it is not.

We are now concerned with the value of $p$, which represents the probability that the algorithm has been successful in its objective. The following chart shows how $p$ increases with $n$.

Note that $p>0.95$ for $n\geq 15$. For $n=40$, $p\approx 10^{-8}$. This means that for larger values of $n$, the algorithm is pretty much guaranteed to be successful. As Wormald noted in 1987,

"Thus, for such values of $n$, Quick-Graph will suffice for practical
purposes."

