# Counting graphs with fixed V+E

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.

-
Do you have any reason to think there will be any kind of useful formula for this? – Gerry Myerson Jun 17 '11 at 0:55
This is very hard for fixed $p$ and $q$, and $n$ isn't a particularly natural parameter here. – Qiaochu Yuan Jun 17 '11 at 0:56
For what it's worth, this is tabulated at oeis.org/A120412 – Gerry Myerson Jun 17 '11 at 1:00
FWIW, this was also posted at mathoverflow.net/questions/68017/counting-graphs – JavaMan Jun 17 '11 at 2:29
Might a starting point be to think about how many planar connected graphs there which obey this condition? – Joseph Malkevitch Sep 1 '11 at 21:05

## 1 Answer

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.

-