5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – bof May 15 '16 at 3:50
  • 2
    $\begingroup$ 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. $\endgroup$ – vadim123 May 15 '16 at 4:04
  • $\begingroup$ "not taking in consideration isomorphism" probably amounts to counting labelled graphs, as @vadim123 seems to interpret the problem. $\endgroup$ – hardmath May 15 '16 at 4:17
1
$\begingroup$

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) $$

$\endgroup$

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.