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

How many cycle-free connected graphs are there on n vertices, none of which has degree >m?

e.g for m=1 there is 1 graph for n=1,2, 0 otherwise. For m=2 there is always 1 graph.

I am particularly interested in the m=4 case, as I was originally trying to count isomers of straight-chain alkanes.

share|cite|improve this question
One approach to the $m=4$ case is to calculate the answer for various small values of $n$ and then see if the result is in the Online Encyclopedia of Integer Sequences. – Gerry Myerson Jan 14 '12 at 6:16
Not in OEIS, the first few terms are 1,1,1,3,5,9,18,35,75. – Angela Richardson Jan 14 '12 at 6:22
It is in OEIS: you missed a $2$ before the $3$. – Brian M. Scott Jan 14 '12 at 7:10
up vote 3 down vote accepted

OEIS sequence A000602 seems to be exactly what you want: ‘Number of n-node unrooted quartic trees; number of n-carbon alkanes C(n)H(2n+2) ignoring stereoisomers’, with extensive references. There’s a table of the values for $n=0$ through $n=60$ here. This sequence is discussed in this paper by Rains & Sloane and in P. Flajolet and R. Sedgewick, Analytic Combinatorics, p. 478; the book is pretty heavy going, but it’s available for free download here. There does not appear to be any nice formula.

The $n=3$ case is OEIS A000672, which also appears to have no nice formula.

share|cite|improve this answer

I see that If $B(z)$ is the OGF of alkanes (EIS A000602), which are unrooted trees, then $B(z) = 1 + z + z^2 + z^3 + 2 z^4 + 3 z^5 + 5 z^6 + 9 z^7 + 18 z^8 + 35 z^9 + \ldots$

But what is the lower or upper bound on the coefficient of $z^n$? It would be really helpful if you could tell something about it.

share|cite|improve this answer
It appears to me that this answer provides the OEIS info that was already provided by Brian M. Scott, and pretty much nothing else. If you have a question, you can ask that in a comment. It is not fit for an answer. And, this answer was 3.5 months later. – Graphth Oct 20 '12 at 2:48

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.