For HW, I need to find the number of isomorphic classes of a simple graph with 7 vertices, each with degree two. I know I could brute-force it by finding all edge sets that fulfill that criteria, but there must be a more efficient way. So, it there a formula that determines number of isomorphic classes of a simple graph with homogenous degree sequence? If my terminology is off, I appreciate your correction.
1
-
$\begingroup$ These are generally called "regular graphs". I doubt there is any general formula for the number of $m$-regular graphs with $n$ vertices, even for fixed $m$ such as 3. Educated brute force is probably the way to go for your homework problem. See oeis.org/A002851 for 3-regular graphs. $\endgroup$– Gerry MyersonApr 11, 2014 at 11:40
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
Hint: A 2-regular graph is a disjoint union of cycles. From there it should be fairly easy to see there are only 2 simple 2-regular graphs on 7 vertices.
answered Apr 11, 2014 at 14:27
-
$\begingroup$ I don't get this answer? What do you mean by disjoint union of cycles $\endgroup$– user143377Apr 15, 2014 at 18:09
-
$\begingroup$ A two-regular graph on $7$ vertices is either $C_{7}$ or $C_{3} \cup C_{4}$. Notice the $C_{3}$ and $C_{4}$ are disjoint, or disconnected. $\endgroup$– ml0105Apr 15, 2014 at 18:18