2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Up to isomorphism or with the vertices labelled? $\endgroup$
    – Asinomás
    Dec 13, 2014 at 21:29
  • $\begingroup$ Oh, from your answer to $(5,9)=10$ I assume it is labelled since otherwise we would have $(5,9)=1$. $\endgroup$
    – Asinomás
    Dec 13, 2014 at 21:32
  • $\begingroup$ Yeah it's labelled. I'm looking into this solution now from a while back: math.stackexchange.com/questions/689526/… $\endgroup$
    – Jasper Lu
    Dec 13, 2014 at 21:42

1 Answer 1

2
$\begingroup$

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)$$

$\endgroup$
5
  • $\begingroup$ I assume by graph you mean simple graph (without loops and multiple edges). $\endgroup$
    – Asinomás
    Dec 13, 2014 at 21:32
  • 2
    $\begingroup$ The question seems to also require the graph to be connected. $\endgroup$ Dec 13, 2014 at 21:33
  • $\begingroup$ Oops, my bad, I shall edit it. $\endgroup$
    – Asinomás
    Dec 13, 2014 at 21:35
  • $\begingroup$ What do you mean by "the connected component" since graphs may have several connected components. Do you any graph with at least one connected component with $j$ vertices? Also, this solution has me worried that there might be some double counting going on. It's very possible to have two different graphs each with two connected components such that if you draw an edge between the two connected components in such a way, those two different graphs become the same graph. $\endgroup$
    – benguin
    Dec 15, 2014 at 10:26
  • $\begingroup$ I am talking about the connected component of $v$. I am classifying according tho that connected component. $\endgroup$
    – Asinomás
    Dec 15, 2014 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.