# number of n-vertex graphs degree $\leq$m

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.

-
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

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.
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.