2
$\begingroup$

I'm trying to find the number of unlabeled graphs with $n$ vertices such that each vertex has degree 2. I know that the edge set for such a graph will have cardinality $n$ and that the maximum number of possible edges for any graph with n vertices is ${n}\choose{2}$ but I'm not exactly sure how to proceed from here.

$\endgroup$
3
  • 1
    $\begingroup$ Are the vertices labeled or unlabeled? $\endgroup$ Sep 21, 2018 at 15:32
  • $\begingroup$ @CarlSchildkraut Was literally just about to ask that $\endgroup$ Sep 21, 2018 at 15:32
  • 1
    $\begingroup$ Unlabeled........... $\endgroup$
    – Hai
    Sep 21, 2018 at 15:33

1 Answer 1

4
$\begingroup$

Hint: A graph on $n$ vertices with each vertex having degree $2$ is simply a graph consisting of disjoint cycles. If the vertices are unlabeled, all you care about are the lengths of each cycle.

$\endgroup$
1

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .