# How many $(x, y)$-paths of length $20$ are there, where $x$, $y$ adjacent vertices in cycle $C_5$?

As the title of the question suggests, let $x$ and $y$ be two adjacent vertices in the cycle $C_5$. How many $(x, y)$-paths of length $20$ are there?

• A couple of clarifying questions: Is the graph only a $C_{5}$, or is there more to it? Do you mean a walk rather than a path? – Luke Mathieson Feb 18 '16 at 23:35
• What did you try? Where did you get stuck? We're happy to help with conceptual problems but just solving homework-style exercises for you is unlikely to really help you. – David Richerby Feb 19 '16 at 0:59
• @LukeMathieson "the cycle $C_5$" rather than "a 5-cycle" seems to be pretty unambiguous that the cycle is the whole graph. Agreed that it should be "walks" to avoid the answer being trivially zero. – David Richerby Feb 19 '16 at 1:00
• @LukeMathieson Some of the literature uses "paths" and "simple paths" to refer to "walks" and "trails", respectively. So the question is on walks (which means the same as paths). – svsring May 30 '16 at 2:11

Hint: consider powers of adjacency matrix of $C_5$ (Wiki: Matrix powers).

You can use the fact that if $A$ is the adjacency matrix of a graph, then the $(i,j)$th entry of $A^k$ is the number of paths of length $k$ from vertex $i$ to vertex $j$. This fact can be proved by induction. So we need to obtain the $(1,2)$th entry of the matrix $A^{20}$. You can compute $A^{20}$ using a computer, or by hand by diagonalizing $A$ (observe that $A$ is a circulant matrix). A SAGE simulation (see below) gives the answer to be 204,820.

sage: c5=graphs.CycleGraph(5)