I am not a mathematician. I've been working on a problem for some time, and I can't seem to be able to grasp the solution.
I need to find an algorithmic way to solve for the number of connected, labeled graphs (I believe those are the correct terms) that can be drawn, given k edges and n vertices.
Most recently, I've tried to solve for the maximum number of vertices, and work my way down by removing edges.
For example, starting with 5 vertices and 10 edges, there is only one graph that can be drawn. 10 of those edges can be removed to create a unique graph, making the solution for (5,9) 10. For (5,8), the solution I get this way is 45 (9 + 8 + ...), and for (5,7) I get 120, or (sigma(8) + sigma(7) + ... + 1), and so on.
This solution seemed to have worked in my head, but when put to the test it does not pass.
Suppose the number we want is $f(n,k)$.The number of graphs with $k$ vertices is $\binom{\binom{n}{2}}{k}$.
We can classify the graphs with $k$ vertices according to the number of vertices in the connected component of $v$, How many of these graphs satisfy the connected component of $v$ has $j$ vertices? There are $\binom{n-1}{j-1}$ ways to select the other vertices. And then we classify on the number of edges in that component, call that number $e$. There are $f(j,e)$ possibilities for the connected components of $e$. And we can add edges between the remainin $n-j$ vertices in $\binom{n-j}{k-e}$ ways. Thus we have obtained:
$$\binom{\binom{n}{2}}{k}=\sum\limits_{j=1}^n\sum\limits_{e=1}^kf(j,e)\binom{n-j}{k-e}$$
From here $$f(n,k)=\binom{\binom{n}{2}}{k}-\sum\limits_{j=1}^{n-1}\sum\limits_{e=1}^kf(j,e)\binom{n-j}{k-e}-\sum\limits_{e=1}^{k-1}f(j,e)$$