Problem

G is the graph
vertex set V = {1,2,3,4}
edges E = (1,2),(1,4),(2,3),(2,3),(2,4)

Find:

1) the adjacency matrix A.
2) the matrix giving the number of 3 step walks.
3) the generating function for walks from point i → j.
4) the generating function for walks from points 1 → 3

Solution

1) The adjacency matrix A is:

A = [[0, 1, 0, 1],
     [1, 0, 2, 1],
     [0, 2, 0, 0],
     [1, 1, 0, 0]]

2) The matrix giving the number of 3 step walks is:

A^3 = [[2, 7, 2, 3],
       [7, 2, 12, 7],
       [2, 12, 0, 2],
       [3, 7, 2, 2]]

3) The generating function for walks from point i → j is:

G(i,j) = (-1)^(i+j) * det(I_{ij}-z*A_{ij})/det(I-z*A)

4) The generating function for walks from points 1 → 3 is:

G(1,3) = (-1)^(1+3) * det(I_{13}-z*A_{13})/det(I-z*A)