How many graphs on [$n$] vertices are isomorphic to $K_n$

193 Views Asked by At

Total Number of Graphs on a vertex set $[n]$ = $2^{\binom{n}{2}}$
Since the total number of isomorphisms is equivalent to total number of bijection $\implies$ $n!$

What it would tell if divide these two $\frac{2^{\binom{n}{2}}}{n!}$, Maybe the lower bound for no of isomorphisms?

Is there any way to find a closed form for this?

1

There are 1 best solutions below

0
On BEST ANSWER

Neither $2^{\binom n2}$ nor $n!$ are relevant.

If a graph with vertex set $[n]$ is isomorphic to $K_n$, then in particular it must have every edge $ij$ for $i,j \in [n]$ (well, with $i\ne j$). That completely determines the edge set. Since we know there is only one possible edge set, there is only one possible graph. That completely answers your question.


In principle, you could do a roundabout calculation. For any $n$-vertex graph $H$:

  • There are $n!$ possible bijections between $[n]$ and $V(H)$. Therefore the graphs on vertex set $[n]$ isomorphic to $H$ have, altogether, $n!$ different isomorphisms to $H$.
  • However, that doesn't mean there's $n!$ such graphs, because each of them might have multiple isomorphisms to $H$. There's a word for that number. $\text{Aut}(H)$ is the automorphism group of $H$, and $|\text{Aut}(H)|$ is its size: the number of isomorphisms from $H$ to itself. A graph isomorphic to $H$ has $|\text{Aut}(H)|$ different isomorphisms to $H$.
  • So there must be $\frac{n!}{|\text{Aut}(H)}$ graphs on vertex set $[n]$ isomorphic to $H$.

In the case of $K_n$, the automorphism group contains all $n!$ possible permutations of $[n]$, so $|\text{Aut}(H)| = n!$. This also tells us that there is only $\frac{n!}{n!} = 1$ graph with vertex set $[n]$ isomorphic to $K_n$.


The calculation $2^{\binom n2}/n!$ tells us something completely different.

From the above, we see that for each $n$-vertex graph $H$, there are at most $n!$ graphs with vertex set $[n]$ isomorphic to $H$ (because there's $n!/a$ of them for some $a \ge 1$). There are also $2^{\binom n2}$ possible graphs with vertex set $[n]$. If we gather them up into classes of graphs isomorphic to each other (a.k.a. isomorphism classes) then there will be at least $2^{\binom n2}/n!$ different classes.

(In fact there will be more. $2^{\binom n2}/n!$ is what we'd get if each class had $n!$ elements. But many of them are smaller.)