Counting paths between vertices
Let G be a graph (simple, multi-, pseudo-, directed or undirected), with
adjacency matrix A with respect to the ordering v1,…,vn. The number
of different paths of length r from vi to vj equals the (i,j)th entry of Ar.
This theorem can be proven using mathematical induction.
In A2, the (a,c) entry is 0?0 + 1?1 + 0?0 + 1?1 = 2.
The number of paths from a to c
The number of paths from a to c
The number of paths from a to c