# Number of paths in regular graphs, where starting and ending nodes are same [duplicate]

Possible Duplicate:
returning paths on cubic graphs

$\hskip2.7in$

In the above undirected, unweighted graph we start with node $Q$. In a single step we can jump to any adjacent node from current node. For given $n$ steps, we've to find out the number of possible ways such that after $n$th step we get back to $Q$, i.e. the starting node. E.g. for $n=1$, we can't get back to $Q$ so answer is $0$, for $n=2$ we can get back to $Q$ in $3$ ways, viz. $Q\to P\to Q$; $Q\to R\to Q$; $Q\to S\to Q$ and so on.

-

## marked as duplicate by draks ..., Sasha, Austin Mohr, Gerry Myerson, J. M.Aug 3 '12 at 8:11

Write down the adjacency matrix $A$ (means label your graph vertices with numbers and write down a matrix, where $A_{km}=1$, if vertex $k$ and $m$ are connected), take the $n$th power of $A$ and look at the element of interest. If you are interested, how many ways from vertex $k$ to $m$ you have after $n$, look at the element $(A^n)_{km}$, which is an element on the diagonal for a returning path.
So in your example, a tetrahedron, $A$ is represented by $$A^1=\pmatrix{ 0 & 1& 1 &1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 }.$$ On the diagonal you find all values equal to $0$, since you can't return in one step, as you've already noticed. Now take the square of $A$. So you'll get $$A^2=\pmatrix{ 3&2&2&2\\ 2&3&2&2\\ 2&2&3&2\\ 2&2&2&3 },$$ where on the diagonal you have all values equal to $3$, also as you've already noticed. The fact that all values are equal follows from your special example. It's complete graph $K_4$, where you can exchange all vertices due to symmetry.
In addition you get the number of ways from $Q$ to any other vertex in $2$ steps, by looking at the corresponding off-diagonal element.