Take the 2-minute tour ×
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.

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|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
    
@ChrisEagle I am asking for your definition, not for the number. –  Phira May 27 '12 at 9:13
1  
@Phira: why is my definition relevant? It's the OP we need to hear from. –  Chris Eagle May 27 '12 at 9:14
2  
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

2 Answers 2

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|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
1  
@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

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:

T:=[1];;

ComputeNextCoefficient:=function()
  local n,f,k,q;
  n:=Size(T)+1;
  f:=0;
  for k in [1..n-1] do
    q:=1+Sum([1..k-1],i->2^i);
    if(k=1) then
      f:=f+q*T[n-1];
      continue;
    fi;
    f:=f+Binomial(n-2,k-1)*q*T[k]*T[n-k];;
  od;
  T[n]:=f;;
end;;

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|improve this answer

Your Answer

 
discard

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.