How many different possible simply graphs are there with vertex set V of n elements - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T04:24:14Z http://mathoverflow.net/feeds/question/57475 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/57475/how-many-different-possible-simply-graphs-are-there-with-vertex-set-v-of-n-elemen How many different possible simply graphs are there with vertex set V of n elements unknown (google) 2011-03-05T17:30:29Z 2011-03-06T04:42:53Z <p>Is V is a set with n elements, how many different simple, undirected graphs are there with vertex set V?</p> http://mathoverflow.net/questions/57475/how-many-different-possible-simply-graphs-are-there-with-vertex-set-v-of-n-elemen/57478#57478 Answer by GH for How many different possible simply graphs are there with vertex set V of n elements GH 2011-03-05T17:53:12Z 2011-03-05T18:31:49Z <p>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 <a href="http://www.ncbi.nlm.nih.gov/pmc/articles/PMC528402/" rel="nofollow">this paper</a> for more information. You can find Pólya's original paper <a href="http://www.springerlink.com/content/9021012252111875/" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/57475/how-many-different-possible-simply-graphs-are-there-with-vertex-set-v-of-n-elemen/57537#57537 Answer by Edwin Clark for How many different possible simply graphs are there with vertex set V of n elements Edwin Clark 2011-03-06T04:42:53Z 2011-03-06T04:42:53Z <p>See <a href="http://oeis.org/A000088" rel="nofollow">http://oeis.org/A000088</a>. 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.</p>