0
$\begingroup$

So like imagine a pentagon for example, so each vertex is adjacent to the next vertex, and then each of those vertices shares an edge with one node in the middle. So there are 6 vertices here, $n = 6$. How many total cycles are in this graph? And then how would you generalize that to any graph with $n \geq 4$ vertices?

I found that for the pentagon example as described, there are $13$ cycles (if I calculated correctly). There are $5$ cycles of length $3 (n-1), 4$ cycles of length $2 (n-2)$, and $4$ cycles of length $5$ ($n-3+1$, the extra $+1$ is for the entire pentagon being a cycle of length $5$). So the formula for this would be $n-1+n-2+n-3+1 = n+n-2+n-3.$

Similarly, for a graph of this description with $n=4$, so a triangle with a node in the middle, there are $7$ cycles. There are $4$ cycles of length $3$ and $3$ cycles of length $4.$ So the formula for this would be $n+n-1.$

I am having a hard time generalizing these into formulas for just a graph with $n$ vertices in general (with an answer in closed form).

$\endgroup$
2
$\begingroup$

The general formula is $(n-1)(n-2) + 1$. I will explain the formula by considering the cases $n=4$, $n=5$, and $n=6$. Your computation for $n=4$ was correct, but your computation for $n=6$ was incorrect.


In the case $n=4$, there are three small cycles of length $3$ in the "interior" of the large triangle. By merging two adjacent small cycles together, we can form cycles of length $4$, of which there are three. Finally, there is the large triangle. So we have $3+3+1$.


In the case $n=5$, there are four small cycles of length $3$ in the interior of the large square. By merging two adjacent small cycles together, we can form cycles of length $4$, of which there are four. By merging three adjacent small cycles together, we can form $4$ cycles of length $5$. Finally, there is the large square. We have $4+4+4+1=13$.


In the case $n=6$, there are five small cycles of length $3$ in the interior. By merging pairs of adjacent small cycles, we can get five cycles of length $4$. By merging triplets of adjacent small cycles, we can get five cycles of length $5$. We can get another five cycle of size $5$ by merging four adjacent small cycles. Finally, there is the large pentagon. This gives $5+5+5+5+1=21$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! How did you derive the general formula from those examples? $\endgroup$ – curlypie99 Apr 14 at 23:20
  • $\begingroup$ @curlypie99 Notice the pattern in the answers for the three cases I wrote out for you. $\endgroup$ – angryavian Apr 15 at 6:34
0
$\begingroup$

You're asking about the number of cycles in the wheel graph $W_n$.

First let's count the cycles that pass through the central node. Such a cycle must use two of the $n-1$ radii, and there are $$\binom{n-1}2=\frac{(n-1)(n-2)}2$$ ways to choose the radii. Then we complete the cycle by choosing one of two arcs, so the number of cycles passing through the central node is $$2\binom{n-1}2=(n-1)(n-2).$$ Finally, there is just one cycle which avoids the central node, so the total number of cycles is $$(n-1)(n-2)+1=n^2-3n+3.$$

| cite | improve this answer | |
$\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.