0
$\begingroup$

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 ${4\choose 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.

enter image description here

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

enter image description here

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

enter image description here

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?

$\endgroup$
2
$\begingroup$

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 k2\rfloor +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/2\rfloor + \lfloor 3/2\rfloor + \lfloor 3/2\rfloor + \lfloor 1/2\rfloor + \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!}{3\cdot1} = 8$ permutations, and $|X^{\sigma}| = 2^{\lfloor 3/2\rfloor + \lfloor{1/2}\rfloor + \gcd(3,1)} = 4$ for each of them.
  • $\lambda = (2,2)$ corresponds to $\frac{4!}{2^2\cdot 2!} = 3$ permutations, and $|X^\sigma| = 2^{\lfloor{2/2}\rfloor + \lfloor 2/2\rfloor + \gcd(2,2)} = 16$ for each of them.
  • $\lambda = (2,1,1)$ corresponds to $\frac{4!}{2\cdot 1\cdot2!} = 6$ permutations, and $|X^\sigma| = 2^{\lfloor{2/2}\rfloor + 2\lfloor{1/2}\rfloor + 2\gcd(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^{6\gcd(1,1)} = 64$ for it.

Altogether we have $\frac{1}{4!}(6\cdot4 + 8\cdot 4 + 3\cdot 16 + 6\cdot 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.)

$\endgroup$
  • $\begingroup$ Thanks. This is going to take me a while to digest. I suppose finding the actual graphs and knowing how many copies they have like I did for n=4 is close to impossible for large n? $\endgroup$ – Rohit Pandey Dec 2 '18 at 7:08
  • 1
    $\begingroup$ For large $n$, there's too many of them to do that quickly. (And finding the number of copies of a given graph - that is, finding the symmetry group - may be quick in practice using a tool like nauty but there is no polynomial-time algorithm.) $\endgroup$ – Misha Lavrov Dec 2 '18 at 16:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.