The following adjacency matrix given by A represents a graph called G:
$$A = \left[ \begin{matrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ \end{matrix} \right] $$
I'm asked to consider whether the following statement is true or false: "There are at most three walks of length 4 between any two distinct vertices of G."
Here's what I've done so far:
I'm trying to use the following theorem: The number of walks of length k from v_i to v_j is equal to the (i,j)-th entry of the matrix A^k
I've taken $$A^4 = \left[ \begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ \end{matrix} \right] $$
So I've got v1 & v2 has one walk and v3 & v4 has one walk.
One has $A^4= \begin{pmatrix} 2 & 3 & 0 & 0 \\ 3 & 5 & 0 & 0 \\ 0 & 0 & 5 & 3 \\ 0 & 0 & 3 & 2 \\ \end{pmatrix} $
As one can see no value greater than $4$ lies outside the diagonal.
This is a possible proof.