Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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 – Gerry Myerson Jun 17 '11 at 1:00
FWIW, this was also posted at – 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

This type of enumeration can be achieved using Polya Theory to attain a generating function. The best reference is Riordan,, 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

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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