15
$\begingroup$

Could someone tell me how to find the number of all non-isomorphic graphs with $m$ vertices and $n$ edges. (The graph is simple, undirected graph)

In my particular problem, $m =20, n=180$

Attempt at solution:

  1. Find the total possible number of edges (so that every vertex is connected to every other one) $k = n(n-1)/2 = 20\cdot19/2 = 190$

  2. Find the number of all possible graphs: $s = C(n,k) = C(190, 180) = 13278694407181203$

Now, I'm stuck because a huge portion of the above number represents isomorphic graphs, and I have no idea how to find all those that are non-isomorphic...

  • 0
    @Gerry Myerson Yes, I thought something was wrong too. That's why I re-asked today and it turns out I was given the incorrect data. It's not 180, but 188 edges. So, complements will have 2 edges and 20 vertices. Therefore, we have 2 non-isomorphic graphs (one, when edges are connected and the other when they are not).2012-02-25

1 Answers 1

9

First off, let me say that you can find the answer to this question in Sage using the nauty generator. If you're going to be a serious graph theory student, Sage could be very helpful.

count = 0 for g in graphs.nauty_geng("20 180:180"):     count = count+1 print count 

The answer is 4613. But, this isn't easy to see without a computer program.

At this point, perhaps it would be good to start by thinking in terms of of the number of connected graphs with at most 10 edges. Then, all the graphs you are looking for will be unions of these. You should be able to figure out these smaller cases. If any are too hard for you, these are more likely to be in some table somewhere, so you can look them up.

Connected graphs of order n and k edges is:

n = 1, k = 0: 1 n = 2, k = 1: 1 n = 3, k = 2: 1 n = 3, k = 3: 1 n = 4, k = 3: 2 n = 4, k = 4: 2 n = 4, k = 5: 1 n = 4, k = 6: 1 n = 5, k = 4: 3 n = 5, k = 5: 5 n = 5, k = 6: 5 n = 5, k = 7: 4 n = 5, k = 8: 2 n = 5, k = 9: 1 n = 5, k = 10: 1 . . . n = 10, k = 9: 106 n = 10, k = 10: 657 n = 11, k = 10: 235 

I used Sage for the last 3, I admit. But, I do know that the Atlas of Graphs contains all of these except for the last one, on P7.

  • 0
    I tried your solution after installing Sage, but with n = 50 and k = 180. The computation never seem to end, is this due to the too-large number of solutions? If so, is there a way to find the number of non-isomorphic, connected graphs with n = 50 and k = 180?2014-04-18