Is V is a set with n elements, how many different simple, undirected graphs are there with vertex set V?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
If you consider isomorphic graphs different, then obviously the answer is $2^{n\choose 2}$. Most graphs have no nontrivial automorphisms, so up to isomorphism the number of different graphs is asymptotically $2^{n\choose 2}/n!$. This goes back to a famous method of Pólya (1937), see this paper for more information. You can find Pólya's original paper here.
answered Mar 5, 2011 at 17:53
$\begingroup$
$\endgroup$
See http://oeis.org/A000088. This is the sequence which gives the number of isomorphism classes of simple graphs on n vertices, also called the number of graphs on n unlabeled nodes. You will also find a lot of relevant references here.
