[Math] Counting non-isomorphic graphs with prescribed number of edges and vertices

Question

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.

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