How many walks of length 8 are there in G

Question

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.

Answer 1

The strongly connected components of the graph are $ABEF$ and $CDGH$, so any path from $A$ to $H$ must use exactly one of $BC$ and $FG$. The choice of edge, together with how many steps are taken in the $ABEF$ cycle, completely determines the path (since there is only one path from one vertex to another in a cycle).

If we use $BC$, we can take $1$ or $5$ steps in $ABEF$. But we cannot use $FG$, since the numbers of steps we would then take in $ABEF$ and $CDGH$ would be congruent to $2\bmod4$ and $3\bmod4$ respectively, for a total path length congruent to $2\bmod4$, whereas $8\equiv0\bmod4$. Hence the two paths you found are the only length-$8$ ones from $A$ to $H$.

Answer 2

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.