# How many different possible simply graphs are there with vertex set V of n elements

Is V is a set with n elements, how many different simple, undirected graphs are there with vertex set V?

-

## 2 Answers

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.

-