I have two questions for my mathematic study. I think I know the answer of the first, but I'm not sure.
A) How many 2 regular graphs are there with verticles 1,2,3,4,5?
I think the answer is 4!/2 = 12
B) How many 3 regular graphs are there with verticles 1,2,3,4,5?
C) How many 3 regular graphs are there with verticles 1,2,3,4,5, 6?
First I thought that the answer of B) must be 4!/3, but that is obviously not true. How to calculate B) and C)? Is there a kind of formula for this sort of problems?
All are vertex labeled
P.S. I just started with my graph theory course, so if it is possible, make your answer a bit easy to understand for me ;)
Thanks in advance!!!
Peter
(A) is correct only if you count the distinct labeled vertices. Notice that the graph in $A$ must be connected. If it is not, then the second component must have fewer than two vertices, which contradicts the regularity. So we have $C_{5}$ as the only graph. Now $Aut(C_{5}) = D_{10}$, giving us $|S_{5}|/|D_{10}| = 12$ such labeled graphs.
(B) There are no such $3$-regular graphs on $5$ vertices. By the Handshake Lemma, we have $\sum_{i=1}^{5} 3 = 15 = 2E$, a contradiction.
(C) Note that the minimal $3$-regular graph is $K_{4}$. So $G$ must be connected. We start with $K_{1, 3}$, a star graph. So the center is $3$-regular. Now we have two left-over vertices. We have two options. Each of the leaves of the star are connected to $v_{5}, v_{6}$. Or $v_{5}$ and $v_{6}$ are adjacent. $v_{5}, v_{6}$ are both adjacent to the second leaf of the star, then we have $v_{5}$ and the first star leaf adjacent, and $v_{6}$ and the third star leaf adjacent.
I leave it to you to count the number of ways you can label such graphs. There are two such graphs up to isomorphism though. Because $G$ is $3$-regular, $K_{1, 3} \leq G$ always. Hence, why I conclude two graphs up to isomorphism.
No, but there are asymptotic bounds. From this Mathoverflow link (https://mathoverflow.net/questions/77730/how-many-p-regular-graphs-with-n-vertices-are-there).
Edit: We have two unique graphs up to isomorphism. What we really want to count is $Aut(\overline{C_{6}}) + Aut(\overline{C_{3} \cup C_{3}})$, where the overline denotes graph complement. Now the automorphism group is the same for a graph and its complement. So we note $Aut(C_{6}) \equiv D_{12}$, so there are $12$ automorphisms of our first graph. Now for $Aut(C_{3} \cup C_{3})$, we have an instance of $D_{6}$ for each $C_{3}$, giving us $12$ elements. We then multiply that $12$ by two, to account for mapping each $C_{3}$ to itself, and mapping the first $C_{3}$ to the second $C_{3}$. And so we have a total of $12 + 2(12) = 36$ such labeled graphs.