# How many cycles are there in graph with $n$ nodes, where each node is adjacent to the next and all nodes are adjacent to a node in the middle?

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).

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

• Thank you! How did you derive the general formula from those examples? Apr 14, 2020 at 23:20
• @curlypie99 Notice the pattern in the answers for the three cases I wrote out for you. Apr 15, 2020 at 6:34

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