Csdrhrt

Given the number of vertices $n$ and the number of edges $k$, I need to calculate the number of possible non-isomorphic, simple, connected, labelled graphs.

My question is very similar to this one. Quoting the accepted answer:

This sequence of numbers is A001187 in the On-Line Encyclopedia of Integer Sequences. If $d_n$ is the number of labelled, connected, simple graphs on $n$ vertices, the numbers $d_n$ satisfy the recurrence
$$sum_kbinom{n}kkd_k2^{binom{n-k}2}=n2^{binom{n}2};$$

from which it’s possible to calculate $d_n$ for small values of $n$. This recurrence is derived as formula (3.10.2) in Herbert S. Wilf, generatingfunctionology, 2nd edition, which is available for free download here.

Example

Let's have $n=4$ (vertices) and $k=3$ (edges). Given my limited knowledge, I'm unable to actually calculate the number of graphs by using the formula above.

Can somebody please walk me through it? I was able to manually count 16 different graphs for this example.

Edit #1

I've found the formula for calculating the total number of simple labelled graphs:
$$binom{binom{n}2}m$$
(Handbook of Discrete and Combinatorial Mathematics, available here, Page 580)

The problem is that the number of graphs given by this formula (for the above example is $20$) also includes all the disconnected graphs.

There is no analytic formula for the number of connected graphs given $n$ labeled nodes and $N$ edges. It has been known, however, since around $1860$ that for $n$ labeled nodes with $n-1$ edges (e.g. $4$ nodes and $3$ edges) the number of connected graphs is $n^{n-2}$.

For any graph of $n$ labeled nodes and $kgtbinom {n-1}2$ edges the graph is always connected and thus the number of connected graphs in that case is equal to the total number of graphs.

For any graph of $n$ labeled nodes and $Klt(n-1)$ edges the graph is never connected. So the number of connected graphs in that case is always $0$.

It is the connected graphs of $n$ labeled nodes with $(n-1)le klebinom{n-1}2$ edges that are non trivial. Carl Wilhelm Borchardt found the formula that we use for the case of $k=n-1$. Cayley popularized it by "expanding" the result.

I just recently found another case. I am currently writing the results now.