Counting simple, connected, labeled graphs with N vertices and K edges

Solution 1:

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 $k\gt\binom {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 $K\lt(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 k\le\binom{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.