3
$\begingroup$

I'd love your help with this question.

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

Thank you very much.

  • 0
    This [MSE link](http://math.stackexchange.com/questions/314103/how-many-2-edge-colourings-of-k-n-are-there) shows how to compute the generating function of non-isomorphic graphs on some number of nodes by the number of edges. The answer to your query is obtained by extracting the relevant coeffcients from these generating functions.2014-06-12

1 Answers 1

1

This type of enumeration can be achieved using Polya Theory to attain a generating function. The best reference is Riordan, http://books.google.com/books?id=zWgIPlds29UC&lpg=PP1&pg=PP1#v=onepage&q&f=false, page 129. See page 143 for the application to counting graphs by |E| and |V|.

If would like to construct such graphs , there is a C program "nauty" developed by Brendan D. McKay, based on his math article http://cs.anu.edu.au/~bdm/nauty/pgi.pdf.