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$
3
-
1$\begingroup$ Are the vertices labeled or unlabeled? $\endgroup$– Carl SchildkrautSep 21, 2018 at 15:32
-
$\begingroup$ @CarlSchildkraut Was literally just about to ask that $\endgroup$– Rushabh MehtaSep 21, 2018 at 15:32
-
1$\begingroup$ Unlabeled........... $\endgroup$– HaiSep 21, 2018 at 15:33
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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, 2018 at 15:34
-
2