Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'd love your help with this question.

Let $n\geq3$ be a fixed integer. How many non-isomorphic graphs with $p$ vertices and $q$ edges are there where $p+q=n$?

Thank you very much.

share|improve this question
2  
I changed the tags. On a different note, this question could do with some attention from the points at mathoverflow.net/howtoask - for example, what is your motivation? How did this question come up? –  David Roberts Jun 17 '11 at 0:41
2  
This duplicates a question at math.stackexchange. math.stackexchange.com/questions/45815/counting-graphs –  Jim Conant Jun 17 '11 at 1:30
2  
Blaise - the usual practice is to not ask in both MO and math.SE at the same time. Usually (as in, almost always) a question will only be suitable for one of them, it may be that the asker misjudges the 'audience', and so needs to swap to the other. –  David Roberts Jun 17 '11 at 1:43

1 Answer 1

Using the Combinatorica package in Mathematica, the command NumberOfGraphs$[p,q]$ returns the number of non-isomorphic graphs with $p$ vertices and $q$ edges. If you want to implement this yourself, you may want to proceed here first.

There is an explicit (but rather complicated) formula which you can find here. The formula is obtained via Pólya's Enumeration Theorem.

Edit: Indeed it is a standard application of Polya theory to obtain formulas for the number of nonisomorphic graphs woth v vertices and e edges. (Counting the number where the total number of vertices and edges is n can be obtained from this.) The standard book on graph enumeration is "Graph enumeration" by Harary and Palmer. There is a web site with many sequences arising from results discussed in the book.

share|improve this answer
2  
Wow! Never in a million years would I have guessed there was an explicit formula, and what a formula it is! –  Jim Conant Jun 17 '11 at 3:46

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.