Number of walks length k in undirected graph

2021-06-20
2 min read

Question: Considering an undirected graph. Given two different vertices $u$ and $v$, how many paths with length of exact $k$, where $k \in \mathbb{N}$, are there from $u \to v$?

For example, consider the following complete graph $K_4$

drawing

For $u = 1, v = 3$ and $k = 3$, there are total $7$ walks: $(1, 4, 2, 3), (1, 2, 4, 3), (1,3,1,3)$.

Closed form solution for complete graph

For a complete graph, we claim the number of walks of length $k$ between any two vertices can be computed by

$$P(n, k) = (n - 1)^{k - 1} - P(n, k - 1)$$

where $P(n, 1) = 1$.

By algebraic reorder $(n - 1)^{k - 1} = P(n, k) + P(n, k - 1)$.

Furthermore, notice that there are $(n - 1)^{k}$ walks of length $k$ that start from $u$. Of those walks, we differentiate two types. The first type of walk has vertex $v$ as last vertex, the second type of walk has vertex $w \neq v$ as last vertex. The first type contributes to walks of length $k$ from $u \to v$. The second type can be extended to walks of length $k + 1$ from $u \to v$. Sum of both is equal to $(n - 1)^{k}$.

General solution by adjacency matrix

Claim: The value at $A^{k}_{ij}$ indicates the number of walk of length $k$ from $i \to j$ where $A$ is the adjacency matrix of the graph.

Proof by induction:

Induction base ($k = 1$): In this case, $A^k$ is simply the adjacency matrix, which contains at $A_{i, j}$ to number of walk of length $1$ from $i \to j$.

Induction step ($k \to k + 1$): In this case, $A_{i, j}^{k + 1}$ can be computed by $A^{k + 1}_{i, j} = \sum\limits_{k = 1}^n A^k_{i, k} \cdot A_{k, j}$. In other words, we just sum up number of walks from $i \to v \neq j$ length $k$, where $v$ is adjacent to $j$.