http://img826.imageshack.us/img826/3527/graphk.jpg

a) Write down the adjacency matrix, F.

This part I can do. (Using the convention that loops count as 1 edge)

The ordering of the vertices are for both rows and columns.

b) Explain why the number of paths of length which begin and end at is always one more than the number of walks of length which begin at and end at .

I'm stuck on this part.

This is what I have done so far:

So I have computed

And I have also computed

Now we can see the that entry in is always 1 more than the entry in

But how do I generalise this for all ?

Thanks!