counting simple, connected graphs 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! 
 A: 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.
A: 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)>

