Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
I'm little bit weak at graphs so would you please explain what does it stands for taking nth power of adjacency matrix and then looking at diagonal element. –  Bharat Kul Ratan Aug 1 '12 at 18:18
    
@tendua if you are interested in solutions without backtracking, see here... –  draks ... Aug 2 '12 at 12:04

Not the answer you're looking for? Browse other questions tagged or ask your own question.