Number of paths in regular graphs, where starting and ending nodes are same

Possible Duplicate:
returning paths on cubic graphs

$\hskip2.7in$Undirected graph of tetrahedron

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.

Solutions Collecting From Web of "Number of paths in regular graphs, where starting and ending nodes are same"

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.