5
$\begingroup$

Given a set of $n$ vertices and the fact that none of them is of degree greater than $2$, how many distinct such graphs are there?

$\endgroup$
5
$\begingroup$

This is OEIS A003292 Number of 4-line partitions of n decreasing across rows.

a(n) is the number of unlabeled graphs on n nodes whose connected components are a path or a cycle. - Geoffrey Critzer, Nov 28 2011

OEIS gives generating function and references which may contain additional information.

G.f.: Product (1 - x^k)^-{c(k)}; c(k) = 1, 1, 2, 2, 2, 2, ....
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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