# Recursive formula for the number of connected labelled graphs with n vertices and k edges

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{.}$$

• This doesn't answer your question, but the formula $\sum_{n,k} T(n,k) \frac{x^n}{n!} y^k = 1+\ln\left( \sum_{n \ge 0} (1+y)^\binom{n}{2} \frac{x^n}{n!} \right)$ from A062734 might help. The Mathematica code on A062734 computes the sequence by looking at the coefficients of the Taylor series of the RHS about $x=0$. – Snowball Dec 3 '14 at 17:45
• That's still interesting — I'm asking for a recursive formula only because I don't think there's a chance of a simple closed formula, but any computable formula will do. – Jacopo Notarstefano Dec 3 '14 at 19:46
• I suggest the first chapter of Harary & Palmer, Graphical Enumeration. – Marko Riedel Dec 3 '14 at 22:24
• There is a recurrence that you may want to refine at this MSE link. – Marko Riedel Dec 4 '14 at 1:21
• Can you elaborate on how exactly that recurrence is computed? The notation is a little strange to me. – gct Dec 17 '14 at 14:18

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.

def numberOfedges(n,k):
t = combination(n,2)
ret = combination(t,k)
if k < combination(n - 1,2) + 1:
for i in range(1,n):
ni = combination(n - 1, i - 1)
x = combination(i,2)
for j in range(i - 1, min(x,k) + 1):
ret -= ni * combination(combination(n - i,2),k - j) * numberOfedges(i, j)
return ret