Probability of randomly choosing identical graph from $G(500,2980)$

22 Views Asked by At

Let $G(500,2980)$ be the set of all graphs with $500$ vertices and $2980$ edges in the Erdos-Renyi model. We are given a specific graph (the details do not matter, but it is supposed to be the US air transportation network with $500$ of the largest airports and $2980$ routes between them), and the question is, what is the probability that we obtain a graph identical to this transportation network when choosing randomly from $G(500,2980)$. We know all the possible random graphs in $G(500,2980)$ are $M=\binom{\binom{500}{2}}{2980}$, so my contention is that the probability is just $\frac{N}{M}$, where $N$ is the number of graphs isomorphic to the transportation network, but is there a way to say more about this probability without knowing any other specific facts about the given graph?