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.
$\begingroup$
$\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
$\begingroup$
$\endgroup$
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.
answered Sep 21 '18 at 15:34
-
2
