Definitions

Definitions Associated With Directed Graphs

Theorem

Let be a labeled digraph with adjacency matrix and be the k-power of .

Then the -th entry of is the number of directed walks of length from to .

Proof

Let us prove it by induction on .

Base Case: The number of directed walks of length is equal to iff ; since , the base of the induction holds true.

Inductive Step: Let the theorem be true for some and let us present the entries of through those of and .

Since , we write .

Since every directed walk of length consists of a directed walk of length from to for some , followed by an edge , we see that the equality above counts all paths of length .