Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

We denote by $C(n,n+k)$ the number of connected graphs on $n$ vertices with $n+k$ edges. I have 2 problems I wish to prove, but after much effort have gotten nowhere with. I would greatly value some help on this, as I have an exam coming up soon and this is the last section of my course I feel I am failing to understand.

Question 1. Show that for every $k \geq -1$ there is some constant $c_k$ such that $C(n,n+k) \sim c_k n^{n + (3k-1)/2}$.

As I said, I've tried to come up with something, but I've really not made any progress; I can't say $(3k-1)/2$ is an expression I've come across before in graph-counting, so I can't see any obvious route to take.

So, knowing this we can say for example that $C(n,n-1) = n^{n-2}$ by Cayley's formula; every connected graph on $n$ vertices with $n-1$ edges must be a tree, and therefore $c_{-1} = 1$. Similarly it can be shown that $c_0 = \sqrt{\pi / 8}$; e.g. by considering graphs with single cycles. Thus my next question may be somewhat obvious:

Question 2. Show that $c_1$ = 5/24; i.e. $C(n,n+1) \sim (5/24)n^{n+1}$. (The question also says: "To save you the trouble of computing the central absolute moments of the standard normal distribution, use that $\int_0^\infty x^3 e^{-x^2/2}dx = 2$." This probably gives a big hint about how to solve the problem, though if you have an alternative method that would be equally welcome.)

Once again, I've gotten nowhere with this one. I think maybe you have to consider it as a case-by-case basis: start with a tree with $n-1$ edges and then consider all the ways you could possibly add 2 edges and the different graph structures that could result. However, I've had no success. Anyway, these questions have me stumped and as I said above, any proof you could provide (or if necessary a source for a proof) would be greatly valued - preferably as soon as you are able please, sadly exams wait for no (wo/)man!

As a matter of interest, I'd also like to know (though less important than the previous 2 questions):

Question 3. Are any other values of $c_i$ known? Is there some clever method which will allow us to calculate lot of these constants, or (as is the case with $i = -1,\,0$) do they all require some clever gimmick unique to that value of $i$?

No worries if you don't know, it's not important but I was just interested in whether they got much academic interest or whether these were questions purely for the sake of asking questions. Thank you very much in advance, I'm sure any help you can give will make a great deal of difference.

share|cite|improve this question
Calculate $C(n,n+1)$ for $n=4,5,6$, say, and look the numbers up in the Online Encyclopedia of Integer Sequences. If it's there, chances are it will come with some links, or references to the literature, that you might find useful. – Gerry Myerson Jun 10 '12 at 12:39
Not to worry, I have found a proof (or rather an allusion to one) in Bollobas' random graphs - 2nd ed. Chapter 5 theorem 5.18 onwards, for anyone interested. Unfortunately I don't have the time to exposit it here; it seems like the grand sum of the results known about these $c_i$ is extremely vast. – Spyam Jun 10 '12 at 18:46
Alas, the paper which contains the answer to Q2 is in Russian, it would seem. – Spyam Jun 10 '12 at 18:50
Some people here read Russian, and some who don't read Russian have access to Math Reviews which might tell them something about what's in the paper, if only you would give a citation. – Gerry Myerson Jun 11 '12 at 0:14

Your Answer


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

Browse other questions tagged or ask your own question.