0
$\begingroup$

How many exists non-isomorphic 4-regular graphs $G = (V,E)$ where $|V|=7$ vertices?

I'm asking for hint to solve it with group theory( if it is possible) and without them

$\endgroup$
2
$\begingroup$

Hint: How many non-isomorphic $2$-regular graphs are there?

$\endgroup$
  • $\begingroup$ Can you elaborate? 2-regular graphs are sets of cycles enumerated by the partition function and two 2-regular graphs can be combined to make a four-regular graph but this only seems to work one way. The OEIS says this is apparently a challenging problem. $\endgroup$ – Marko Riedel Nov 29 '14 at 22:27
  • $\begingroup$ @MarkoRiedel The question asks for the number of nonisomorphic $4$-regular graphs on $7$ vertices. In that special case, the $4$-regular graphs are the complements of the $2$-regular graphs . . . oh, see dtldarek's answer! $\endgroup$ – bof Nov 29 '14 at 23:37
  • $\begingroup$ (+1) $4+2 = 6 = 7-1$ I cannot believe I missed this. $\endgroup$ – Marko Riedel Nov 29 '14 at 23:59
2
$\begingroup$

Hint:

  • How does a complement of such a graph looks like?
  • How many such non-isomorphic complements exist?

I hope this helps $\ddot\smile$

$\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.