Say I have a wheel graph $W_n$ where $n$ represents the number of vertices and $n \geq 3$.
Is there a general formula to determine the number of cycles there are in total or the number of cycles of a particular length? What about the number of paths of a particular length?
Edit: I found that the total number of cycles is $(n-2)(n-1) + 1$ but I don't fully understand why that's the case.
$\endgroup$ 11 Answer
$\begingroup$Let's examine the Wheel graphs for small values of $n$:
Now let's try and count the cycles:
- There is one cycle that doesn't pass through the center
- There are several cycles passing through the center. To construct one such cycle first select the 2 vertices that will connect to the center (there are $\binom{n-1}{2}$ choices) and then for each such pair we can have 2 cycles: one that takes the "upper" path and one that takes the "lower" path so by the rule of product we have $2\cdot \binom{n-1}{2}$ cycles passing through the center.
In total we have $1 + 2\cdot \binom{n-1}{2} = 1 + (n-1)(n-2)$ cycles on the wheel graph with $n$ vertices.
To count the number of cycles of specific length a simple argument like the above cannot work because there are some cases that need to be considered. For example, to construct a cycle of length $k$ passing from the center we can select a vertex $v$ that will connect to the center, and the other vertex adjacent to the center will be one such that its distance from $v$ along the circumference will be $k-2$. There can be $0$, $1$, or $2$ such vertices. Also, you should make sure that you are not double counting cycles.
$\endgroup$
