# How many connected, simple graphs are on n vertices

I'm trying to find a formula that will give me the number of connected, simple graphs on n vertices, not taking in consideration isomorphism.

I though that it can be done by taking the difference between the total number of possible graphs and disconnected graphs. We will have :

$2^{\binom{n}{2}}$ , where $\binom{n}{2}$ will determine the number of possible edges(this will give us total number of possible graphs)

The disconnected graphs will consist of $n-2, n-3 ...$ edges(since $n-1$ is a tree). The number of disconnected graphs will depend on number of vertices, so I though it would be equal to $\sum_{i=2}^{n-1}(2^{\binom{n}{2} -i})$.

Altogether : $2^{\binom{n}{2}}-\sum_{i=2}^{n-1}(2^{\binom{n}{2} -i})$ . And I'm stuck here. What would be a correct approach to this problem?

• A graph with $n$ vertices and $n-1$ edges is a tree if it's acyclic. There is a disconnected graph with $4$ vertices and $3$ edges (a triangle plus an isolated vertex). For every $n$ there is a disconnected graph with $n$ vertices and $\binom{n-1}2$ edges. – bof May 15 '16 at 3:50
• oeis.org/A001187 has a lot of info. There doesn't seem to be a nice formula, but there are generating functions and values for small n. – vadim123 May 15 '16 at 4:04
• "not taking in consideration isomorphism" probably amounts to counting labelled graphs, as @vadim123 seems to interpret the problem. – hardmath May 15 '16 at 4:17

## 1 Answer

We will reduce the problem of counting the number of labeled simple graphs on $n$ vertices to enumerating partitions of $n$. Our main strategy is to use Mobius inversion on the partition lattice.

Let $G=(V,E)$ be a graph on $n$ vertices. For any subgraph $G'=(V,E')$, where $E'\subseteq E$, we denote $C_{G'}$ to be the partition of vertices corresponding to the connected components of $G'$. We now define $g: \Pi_n \to \mathbb{Z}$ and $f: \Pi_n \to \mathbb{Z}$ as follows. Let $g(B)$ be the number of simple subgraphs $G'=(V,E')$ such that $C_{G'}=B$, and let $f(B)$ be the number of simple subgraphs $G'=(V,E')$ such that $C_{G'}\le B$. Then $$f(B)= \sum_{A\le B} g(A)$$

We call a partition of $n$ to be type $(k_1,k_2,\dots,k_n)$ if the partition contains $k_i$ blocks of size $i$. Now if $B\in \Pi_n$ has type $(k_1,k_2,\dots,k_n)$, then $$f(B)= 2^{\sum_{i=2}^n k\dbinom{i}{2}}$$ By Mobius Inversion, we have $$g(\widehat{1})=\sum_{A\le B}\mu_{\Pi_n}(A,\widehat{1})f(A)$$ Let $\sum_{i=1}^n k_i=k$. Then $|A|=k$, and $[A,\widehat{1}]\cong \Pi_k$. Hence $$\mu_{\Pi_n}(A,\widehat{1})=\mu_{\Pi_k}(\widehat{0},\widehat{1})=(-1)^{k-1}(k-1)!$$ Note that there are $$\frac{n!}{\prod_{i=1}^n k_i!i!^{k_i}}$$ partitions of $n$ of type $(k_1,k_2,\dots,k_n)$. Thus the number of labeled simple graphs on $n$ vertices is $$g(\widehat{1})=\sum_{\substack{(k_1,k_2,\dots,k_n) \\ \sum_{i=1}^n ik_i=n}} \left[2^{\sum_{i=2}^n k\dbinom{i}{2}}\right]\left[(-1)^{-1+\sum_{i=1}^n k_i}\right]\left(-1+\sum_{i=1}^n k_i\right)!\left(\frac{n!}{\prod_{i=1}^n k_i!i!^{k_i}}\right)$$