10
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ 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? $\endgroup$
    – David Roberts
    Jun 17, 2011 at 0:41
  • 4
    $\begingroup$ This duplicates a question at math.stackexchange. math.stackexchange.com/questions/45815/counting-graphs $\endgroup$
    – Jim Conant
    Jun 17, 2011 at 1:30
  • 5
    $\begingroup$ 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. $\endgroup$
    – David Roberts
    Jun 17, 2011 at 1:43

1 Answer 1

23
$\begingroup$

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.

$\endgroup$
1
  • 7
    $\begingroup$ Wow! Never in a million years would I have guessed there was an explicit formula, and what a formula it is! $\endgroup$
    – Jim Conant
    Jun 17, 2011 at 3:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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