Ytukyg

Let's say I have n nodes that are distinct from one another. The number of possible edges is - $n(n-1)/2$. And so, the total number of graphs becomes $2^{n(n-1)/2}$ (each edge can exist or not). Now, let's make all the nodes identical. Some of these $2^{n(n-1)/2}$ graphs now become identical - meaning we can move around the vertices of one of them to get another one. But there are still a certain number of distinct graphs.

For example, let's take n=4. The total edges are ${4choose 2}=6$. So, the total number of graphs if the nodes were distinct becomes $2^6=64$.

Now if we make the nodes identical, we can break these up as follows:

1) Nodes with one or five edges: there are six such graphs. But if the nodes are distinct, they become just one since each of the six can be converted to any other by simply moving the nodes around.

2) Similarly, we can look at nodes that have two or four edges connected:

3) And finally, cases where we have three edges connected (20 graphs)

So, we get 9 distinct graphs. Add 2 more for all nodes connected and no nodes connected and this gives us 11 for n=4.

Now the question is, how to we do this for general n? Closed form would be great but if not, can we use a computer somehow to get it for reasonable n's?

There is no closed formula. Computing the number of graphs is painful. Probably it is best to do as bof does in the comments and look the answer up on OEIS.

Given a permutation $sigma$ of $n$ vertices, let $X^sigma$ denote the set of all labeled graphs that are unchanged when we apply $sigma$. Then Burnside's lemma says that the number of unlabeled graphs is given by the calculation
$$
frac{1}{n!} sum_{sigma in S_n} |X^sigma|.
$$
To compute $|X^sigma|$, we reason from the cycle decomposition.

1. If $sigma$ has a cycle of length $k$, the number of ways to choose the edges between vertices of that cycle is $2^{lfloor k/2 rfloor}$. (If $v_1, v_2, dots, v_k$ are the vertices of the cycle, then once you decide if edge $v_1 v_i$ is present for $2 le i le lfloor frac k2rfloor +1$, this determines the behavior of edges $v_2 v_{i+1}$, $v_3 v_{i+2}$, and so on.)




2. For every two cycles of lengths $k$ and $l$ in $sigma$, the number of ways to choose the edges between their vertices is $2^{gcd(k,l)}$ for similar reasons. If the first cycle is on vertices $v_1, dots, v_k$ and the second on vertices $w_1, dots, w_l$, then the behavior of edge $v_1 w_i$ is the same as that of edge $v_2 w_{i+1}$, $v_3 w_{i+2}$, and so on. This gives $text{lcm}(k,l)$ different edges determined by $v_1 w_i$, and so there are $frac{kl}{text{lcm}(k,l)} = gcd(k,l)$ binary choices to make.

So, for instance, the number of $9$-vertex graphs fixed by the permutation $(1;2);(3;9;6);(4;8;7);(5)$ is
$$
2^{lfloor 2/2rfloor + lfloor 3/2rfloor + lfloor 3/2rfloor + lfloor 1/2rfloor + gcd(2,3) + gcd(2,3) + gcd(2,1) + gcd(3,3) + gcd(3,1) + gcd(3,1)} = 2^{11}.
$$
Because we only care about the lengths of the cycles, this is also the number of $9$-vertex graphs fixed by $(1;2);(3;4;5);(6;7;8);(9)$ or any other permutation in the same conjugacy class. So instead of summing over all permutations, we can sum over all partitions $lambda$ of $n$. We need to know the number $N(lambda)$ of permutations in that conjugacy class; if $lambda$ has $a_i$ parts of size $i$ (so that the permutations have $a_i$ cycles of length $i$) then there are $N(lambda) = frac{n!}{prod_i (a_i)^i cdot a_i!}$ such permutations.

Altogether, we get a sort of formula: the number of unlabeled graphs is
$$
sum_{lambda mathbin{vdash} n} frac{N(lambda)}{n!} prod_i 2^{lfloor lambda_i/2 rfloor} prod_{i < j} 2^{gcd(lambda_i, lambda_j)}.
$$
For example, when $n=4$, the partitions of $n$ are $(4)$, $(3,1)$, $(2,2)$, $(2,1,1)$, and $(1,1,1,1)$, and we have a term for each of them.

• 
  $lambda = (4)$ corresponds to $frac{4!}{4} = 6$ permutations, and $|X^sigma| = 2^{4/2} = 4$ for each of them.


• 
  $lambda = (3,1)$ corresponds to $frac{4!}{3cdot1} = 8$ permutations, and $|X^{sigma}| = 2^{lfloor 3/2rfloor + lfloor{1/2}rfloor + gcd(3,1)} = 4$ for each of them.


• 
  $lambda = (2,2)$ corresponds to $frac{4!}{2^2cdot 2!} = 3$ permutations, and $|X^sigma| = 2^{lfloor{2/2}rfloor + lfloor 2/2rfloor + gcd(2,2)} = 16$ for each of them.


• 
  $lambda = (2,1,1)$ corresponds to $frac{4!}{2cdot 1cdot2!} = 6$ permutations, and $|X^sigma| = 2^{lfloor{2/2}rfloor + 2lfloor{1/2}rfloor + 2gcd(2,1) + gcd(1,1)} = 16$ for each of them.


• 
  $lambda = (1,1,1,1)$ corresponds to only $1$ permutation (the identity) and $|X^{sigma}| = 2^{6gcd(1,1)} = 64$ for it.

Altogether we have $frac{1}{4!}(6cdot4 + 8cdot 4 + 3cdot 16 + 6cdot 16 + 64) = 11$ graphs.

(Asymptotically, the last term, corresponding to the identity permutation, will be the dominant one for large $n$, and we get around $2^{binom n2}/n!$ graphs. In other words, most graphs are completely asymmetric, and we can just pretend all of them are without too much error.)