Let $n,k$ be integers such that $n – 1 \le k \le {n \choose 2}$. Let $T(n, k)$ be the number of connected, simple graphs without self-loops on $n$ labelled vertices having exactly $k$ edges. Can we give an expression for $T(n,k)$ in terms of $T(m,h)$ for $m < n$ or $h < k$ (that is, a recursive formula)?
$T(n, k)$ is sequence A123527 on the OEIS: http://oeis.org/A123527.
Variations on this question have been asked before on this site (for instance: here), but I wasn't able to piece together a recursive formula from their answers. My motivation is to write a program that computes it for small $n$, for which a recursive formula can be used.
So far I've noticed that a few base cases are easy to compute. In fact, if $k = n – 1$ then $T(n, k)$ is counting the number of trees on $n$ vertices, which, by Cayley's formula, is $$T(n, n – 1) = n ^ {n – 2}\text{,}$$ while if $k \ge {n – 1 \choose 2} + 1$ then every graph is surely connected, therefore $$T(n, k) = {{n \choose 2} \choose k}\text{.}$$
Best Answer
I know I am late but I had the same question and came up with following recurrence. I hope this helps somebody who comes across this.