[Math] Number of paths of length $4$

Question

I have a graph that look like the graph below. I need to show that between every pair of vertices there is at least a path of length $4$. I need also to find how many such as these paths is there between $a$ and $b?$

  c
 | \
 |  \
 a----b----e
 |   /
 |  /
  d 

I know that I have to start by setting up a adjacency matrix, which is:

       0    1   1   1   0
       1    0   1   1   1
       1    1   0   0   0
       1    1   0   0   0
       0    1   0   0   0

But I am not sure how to continue here to answer the questions above.

Answer 1

The $k$th power of the adjacency matrix $A$ has its entry in row $i$ column $j$ the number of paths of length exactly $k$ from vertex $i$ to vertex $j.$ This can be seen to work by seeing how matrix multiplication works for some specific adjacency matrices of not to large size and some moderate values of $k.$

So to show every vertex is connected to each other vertex by a path of length at least 4, to be complete one would look at the sequence $A^4,A^5,A^6,\cdots$ and see if some entry of at least one of these in position $(i,j)$ is positive. Of course you can stop if you ever get a single power 4th or higher of the matrix with all positive entries.

Note: as M. Vinay points out, the powers of the adjacency matrix have entries giving the number of walks, rather than paths, of a given length between the vertices. Another note is it matters whether you want to make sure paths from a vertex to itself exist of length 4 or more, or do not require that. In the latter case you just don't need to consider the diagonal elements being 0 or positive in the above.

It seems likely in your example a relatively small power of $A$ at 4 or more power will have all positive entries, since the graph is connected.

Your other question is easier since you want the number of paths of length 4 between two specific vertices. So for that you only need look at $A^4$ and find the entry in the $(i,j)$ position, where $i,j$ are the specific vertices.