Let G be the following directed graph
How many walks of length 8 are there in G, from vertex A to vertex H?
One of the walk I found is this:
$A \to B$, $B \to F$, $F \to E$,$E \to A$, $A \to B$,$B \to C$, $C \to D$,$D \to H$
The other one is this:
$A \to B$,$B \to C$,$C \to D$,$D \to H$,$H \to G$,$G \to C$,$C \to D$,$D \to H$
Am I doing this right? For the second walk, I am a little sceptical about my answer because it uses vertex H twice (my thought was that because it ends at H, the vertex can only be used once)
Can anyone help me with this? Any help is truly appreciated. Thank you in advance.
Best Answer
Those are two walks valid walks.
In general if $A$ is the adjacency matrix (i.e., $a_{ij} = 1$ if we have $i \to j$). Then $ij$th entry of $A^k$ is the number of walks from $i$ to $j$.
We can prove this via induction. Clearly the base is true. For the inductive step, lets note the following
$$A^{l+1}_{ij} = \sum_{k=1}^n A^l_{ik}a_{kj}.$$
For any walk ending at $j$ we must have come from an $k$ such that $k \to j$. For each such $j$ we have $A^l_{ik}$ many walks from $i$ to $k$. Thus summing over these gives us all of the walks of length $l+1$ from $i$ to $j$.
For this specific graph Parcly Taxel gives another way to compute the answer.