# Counting non-isomorphic graphs with prescribed number of edges and vertices

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.

Crossposted at MSE.

• 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
• This duplicates a question at math.stackexchange. math.stackexchange.com/questions/45815/counting-graphs – Jim Conant Jun 17 '11 at 1:30
• 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

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.
Edit: Indeed it is a standard application of Pólya theory to obtain formulas for the number of nonisomorphic graphs with $p$ vertices and $q$ 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 "Graphical enumeration" by Harary and Palmer. There is a web site with many sequences arising from results discussed in the book.