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

I've been thinking about this for a few days, but I haven't found a general solution yet. How many distinct simple, connected, undirected graphs are there of n labelled vertices? For example, there is one for n = 2 and there are four for n = 3. Thanks in advance!

share|cite|improve this question
What is a "simply connected" graph? A tree? – Phira May 27 '12 at 9:04
I count three for $n=3$. – Chris Eagle May 27 '12 at 9:12
@Phira: why is my definition relevant? It's the OP we need to hear from. – Chris Eagle May 27 '12 at 9:14
Ach, sorry! I meant "simple, connected," not "simply connected," which I don't think is a term in graph theory. That must be the source of confusion. – Chris May 27 '12 at 9:17
This is OEIS sequence A001187. When looking for this sort of sequence, it's a good idea to first search OEIS, both by text search and by determining the first few terms and searching with them. – joriki May 27 '12 at 9:20

The number of all labelled simple graphs on $n$ vertices is $g_n=2^{\binom n 2}$ because you can decide for each edge whether to include it.

Now, let $G(x)=\sum_{n=0}^{\infty} g_n \dfrac {x^n}{n!}$, let $c_n$ be the number of connected labelled simple graphs on $n$ vertices and let $C(x)=\sum_{n=0}^{\infty} c_n \dfrac{x^n}{n!}$

Then, you have the relationship

$$ G(x)=\exp (C(x)) $$

which permits the calculation of the numbers $c_n$, but does not imply a simple formula.

share|cite|improve this answer
The function G(x) (above) is undefined for x != 0 as g_n grows faster than n!. To see this, take the log_2 of both 2^(n choose 2) and n! leaving (n choose 2) = n(n-1)/2 and SUM log_2(k) for k from 1 to n. It is also unclear how you get from the definitions of G(x) and C(x) to the relationship G(x) = exp(C(x)) as there is no clear use of simplicity or connectedness shown. Is there a piece missing? – user59414 Jan 23 '13 at 20:56
@Just, it's a formal power series, it doesn't have to converge. A common technique in the use of generating functions. – Gerry Myerson Jan 24 '13 at 4:51
When you say permits the calculation, how would you go about it? – Theo Belaire Dec 7 '14 at 18:57

These numbers are given by the Tutte polynomial $T_n(x,y)$ of the complete graph at the point $(x,y)=(1,2)$. There are reasonably easy to compute formulae for this polynomial; e.g. this paper by Igor Pak gives the formula: $$T_{n+1}(x,y)=\sum_{k=1}^n \binom{n-1}{k-1} (x+y+y^2+\cdots+y^{k-1})\ T_k(x,y)\ T_{n-k+1}(x,y).$$

Here's some GAP code that implements this:


  local n,f,k,q;
  for k in [1..n-1] do
    if(k=1) then

Then we run it by something like:

while(Size(T)<600) do ComputeNextCoefficient(); od;

It took 27 seconds to compute the numbers for $1,2,\ldots,600$.

gap> T[600];
<integer 123...752 (54096 digits)>
share|cite|improve this answer
This has been awhile, but can this be used to compute the number of graphs on n vertices with k edges? I'm a little confused about what the recurrence is compute as the notation seems a little odd to me. Do the T_n terms represent individual coefficients? – gct Dec 16 '14 at 4:40

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.