Is V is a set with n elements, how many different simple, undirected graphs are there with vertex set V?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
|
|
|
|
|
2
|
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. |
|||
|
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
2
|
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. |
||
|
|
