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?

Question

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

Answer 1

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

Answer 2

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