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.

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ Are the vertices labeled or unlabeled? $\endgroup$ – Carl Schildkraut Sep 21 '18 at 15:32
  • $\begingroup$ @CarlSchildkraut Was literally just about to ask that $\endgroup$ – Don Thousand Sep 21 '18 at 15:32
  • 1
    $\begingroup$ Unlabeled........... $\endgroup$ – Hai Sep 21 '18 at 15:33
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.

|cite|improve this answer
$\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.