2
$\begingroup$

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!

  • 0
    What is a "simply connected" graph? A tree?2012-05-27
  • 0
    I count three for $n=3$.2012-05-27
  • 0
    @ChrisEagle I am asking for your definition, not for the number.2012-05-27
  • 0
    Not necessarily a tree—it can have cycles. That's also why there are four for n=3, rather than just three.2012-05-27
  • 1
    @Phira: why is my definition relevant? It's the OP we need to hear from.2012-05-27
  • 0
    @Chris: So does "simply connected" just mean "connected" then?2012-05-27
  • 0
    @ChrisEagle Sorry.2012-05-27
  • 1
    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.2012-05-27
  • 0
    Rats. I thought he was asking about trees. Funny thing is, I'd been thinking of asking that exact same question. Depending on the results of this, I still might.2012-05-27
  • 2
    This is [OEIS sequence A001187](http://oeis.org/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.2012-05-27
  • 0
    I have written an answer based on the word "labelled", but I am still unsure why the word "distinct" is used in the question.2012-05-27
  • 0
    See also [this interesting question](http://math.stackexchange.com/questions/68457/number-of-connected-graphs-on-labeled-vertices-counted-according-to-parity).2012-05-27
  • 0
    @Phira Thanks for the answer. Unfortunately, I'm just some kid without much of a mathematics background, so I don't quite get most of your explanation. The first line makes sense, but what was your thought process in introducing G(x) and C(x), and what does the exp function do? Thanks!2012-05-27
  • 0
    @Chris Do you understand the symbols I have written? As in: Do you know exp and the sigma notation for sums?2012-05-27
  • 0
    @Phira I'm perfectly comfortable with sigma notation, but not this exp thing.2012-05-27
  • 0
    @Chris exp is the exponential function. http://en.wikipedia.org/wiki/Exponential_function2012-05-27
  • 0
    Oh. Well, now I feel silly. Thank you very much for the answer.2012-05-27

2 Answers 2

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.

  • 0
    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?2013-01-23
  • 1
    @Just, it's a formal power series, it doesn't have to converge. A common technique in the use of generating functions.2013-01-24
  • 0
    When you say permits the calculation, how would you go about it?2014-12-07
1

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];

  • 0
    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?2014-12-16