How many distinct graph can I have with n nodes (No label on Nodes, nor weight on Edges)? Is there a formula? For example for a graph with 3 nodes I can just have a linear shape and a Triangular.
1 Answers
While we do have formulas for the number of non-isomorphic graphs, it appears that these formulas are quite hard to evaluate. The OEIS lists the numbers of distinct graphs for many numbers of nodes and includes references to papers that have worked out the details.
The number of distinct graphs grows extremely quickly as a function of the number of nodes. Asymptotically, the number of n-node non-isomorphic graphs is approximately 2n(n - 1) / 2 / n!. That intuitively makes sense; the numerator here counts the number of graphs on n labeled nodes, and the denominator counts the number of ways you can rearrange the labels on those nodes. Check the OEIS for links to proofs of this result.
Related