1
$\begingroup$

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.

1 Answers 1

4

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.

  • 0
    @tendua if you are interested in solutions without backtracking, see [here](http://math.stackexchange.com/q/177722/19341)...2012-08-02