Is V is a set with n elements, how many different simple, undirected graphs are there with vertex set V?
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
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. 


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. 

