Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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...

share|improve this question
    
Hint: consider the complements of your graphs. –  Yuval Filmus Feb 24 '12 at 18:23
    
Thanks for the hint, but I still don't get it, because I don't really see how you can consider every single complement. I mean, the number is huge... –  user825089 Feb 24 '12 at 18:33
1  
How many edges will the complements have? If two complements are isomorphic, what can you say about the two original graphs? Or, if the two complements are not isomorphic? –  Graphth Feb 24 '12 at 19:14
    
For each graph, the complement to this graph is going to have 10 edges (190-180). I see what you are trying to say. I have to figure out how many non-isomorphic graphs with 20 vertices and 10 edges there are, right? –  user825089 Feb 24 '12 at 19:23
    
I might be wrong, but a vertex cannot be connected "to 180 vertices". There are a total of 20 vertices, so each one can only be connected to at most 20-1 = 19. Also, the complete graph of 20 vertices will have 190 edges. Our graph has 180 edges. So, when we build a complement, we remove those 180, and add extra 10 that were not present in our original graph. So, it's 190 -180. I don't really see where the -1 comes from. Anyhow, you gave me an incredibly valuable insight into solving this problem. If you consider copying your +1 comment as a standalone answer, I'll gladly accept it:)! –  user825089 Feb 24 '12 at 20:16

1 Answer 1

up vote 6 down vote accepted

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.

share|improve this answer
    
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? –  Rodolphe Apr 18 at 20:05

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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