Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose that we had a set of vertices labelled $1,2,\ldots,n$.

There will several ways to connect vertices using edges. Assume that the graph is simple and connected.

In what efficient (or if there is no efficient way, you can just tell me whatever procedure you can think of) way do we be able to calculate the number of possible ways the graph can be made? (even if some graphs are isomorphic to each other, they are counted as separate cases.)

share|cite|improve this question
I don't understand what "no subgraph of a graph is at least connected to one of other subgraphs". – Arturo Magidin Jun 7 '12 at 2:33
Do you allow loops (edges with the same vertex at both ends)? Do you allow more than one edge between two vertices? Finally, can you explain the parenthetical comment in the second paragraph? It’s not clear as it stands. – Brian M. Scott Jun 7 '12 at 2:34
If you are talking about simple connected graphs, then the sequence is A001349 in the On-line encyclopedia of integer sequences. There is no formula given, but there are references for computing the numbers. – Arturo Magidin Jun 7 '12 at 2:35
@ArturoMagidin yes, I am talking about simple connected graphs. – Shoeinger Veronica Jun 7 '12 at 2:40
@ShoeingerVeronica: That's called a "connected" graph. "Simple" means there are no multiple edges between the same two vertices and no loops. So you are talking about the sequence I refered to; there are citations to articles about how to count the number, presumably as efficiently as is known. – Arturo Magidin Jun 7 '12 at 2:40
up vote 12 down vote accepted

There are $\binom{n}2=\frac12n(n-1)$ pairs of distinct points. If you do not allow loops or multiple edges, each of these pairs determines one possible edge, and you can have any subset of those possible edges. A set with $\binom{n}2$ members has $2^{\binom{n}2}$ subsets, so there are $2^{\binom{n}2}$ possible graphs without loops or multiple edges.

If you demand that the graphs be connected, the problem becomes very much harder. From your final comment I take it that you are in effect counting labelled graphs. This sequence of numbers is A001187 in the On-Line Encyclopedia of Integer Sequences. If $d_n$ is the number of labelled, connected, simple graphs on $n$ vertices, the numbers $d_n$ satisfy the recurrence


from which it’s possible to calculate $d_n$ for small values of $n$. This recurrence is derived as formula (3.10.2) in Herbert S. Wilf, generatingfunctionology, 2nd edition, which is available for free download here.

According to MathWorld, Brendan McKay’s software package nauty includes a routine that efficiently enumerates such graphs; it’s available here.

If you count unlabelled graphs instead, so that you don’t count isomorphic graphs separately, you get the sequence mentioned by Arturo in the comments.

share|cite|improve this answer
There is a mistake in the right hand side – Sergio A. Yuhjtman Oct 22 '15 at 15:00
@Sergio: There is indeed; thanks very much. Fixed now. – Brian M. Scott Oct 22 '15 at 18:11
@BrianM.Scott Could you have a look at my question :…. – sasha May 10 at 10:47

You can use exponential generating functions for this. The exponential generating functions $C(x)$ for connected labeled graphs and $D(x)$ for all labeled graphs are related by

$$D(x)=\mathrm e^{C(x)-1}\;,$$

which you can show using the decomposition of a labeled graph into its connected components.

As others have noted, we have

$$ D(x)=\sum_{n=0}^\infty\frac{2^{n(n-1)/2}}{n!}x^n\;, $$


$$ \begin{align} C(x) &= 1+\log\sum_{n=0}^\infty\frac{2^{n(n-1)/2}}{n!}x^n \\ &= 1+\log\left(1+x+\frac2{2!}x^2+\frac8{3!}x^3+\frac{64}{4!}x^4+\dotso\right) \\ &= 1+x+\frac1{2!}x^2+\frac4{3!}x^3+\frac{38}{4!}x^4+\dotso \;. \end{align} $$

Thus there are $1,1,1,4,38,\dotsc$ different connected graphs on $0,1,2,3,4,\dotsc$ labeled vertices.

share|cite|improve this answer

As I indicated in the comment, this is sequence A001349 in the On-Line Encyclopedia of Integer Sequences. There is no closed formula listed, but there are a couple of references to computer calculations and algorithms. I suggest that's the place where you want to start.

share|cite|improve this answer

IF it is a simple, connected graph, then for the set of vertices {v: v exists in V}, v is adjacent to every other vertex in V. This type of graph is denoted Kn. For Kn, there will be n vertices and (n(n-1))/2 edges.

To determine how many subsets of edges a Kn graph will produce, consider the powerset as Brian M. Scott stated in a previous comment. If S is a finite set with n elements, then the powerset of S will have 2^n elements where n is the number of elements in the set S.

Assuming that the n in Kn is any non-negative integer, then shouldn't the set be considered countably infinite? If so, this would make the cardinality of the powerset Alepha 0.

share|cite|improve this answer
Please use the right math formatting, see e.g. here. – Keep these mind Apr 8 '13 at 8:07

We can also 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) $$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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