What paths between vertices is this method actually counting?

Question

Context

From Discrete Mathematics and Its Applications by Kenneth H. Rosen:

Let $G$ be a graph with adjacency matrix $A$ with respect to the ordering $v_1, v_2, ..., v_n$ of the vertices of the graph (with directed or undirected edges, with multiple edges and loops allowed). The number of different paths of length $r$ from $v_i$ to $v_j$ where $r$ is a positive integer, equals the $(i, j)$th entry of $A^r$.

From this website on the same approach:

Paths don't have to be simple, i.e. vertices and edges can be visited any number of times in a single path.

---

The case that isn't working out

I am trying to work with the complete graph $K_5$.

The adjacency matrix $A = $ $\begin{bmatrix} 0&1&1&1&1\\ 1&0&1&1&1\\ 1&1&0&1&1\\ 1&1&1&0&1\\ 1&1&1&1&0\end {bmatrix}$ gives paths of length $1$.

$A^2 = $ $\begin{bmatrix} 4&3&3&3&3\\ 3&4&3&3&3\\ 3&3&4&3&3\\ 3&3&3&4&3\\ 3&3&3&3&4\end {bmatrix}$ gives paths of length $2$.

If I were to verify the entry ${A^2}_{(1,1)}$, it would be the number of paths of length $2$ which start and end at vertex $1$. This would list out to be:

1. $1 - 2 - 1$
2. $1 - 3 - 1$
3. $1 - 4 - 1$
4. $1 - 5 - 1$

This gives me confidence that in a path using this method, the same edge can be visited back and forth without any restriction.

Let us now consider paths of length $4$:

$A^4 = $ $\begin{bmatrix} 52&51&51&51&51\\ 51&52&51&51&51\\ 51&51&52&51&51\\ 51&51&51&52&51\\ 51&51&51&51&52\end {bmatrix}$

From ${A^4}_{(1,1)}$, it is clear that there are $52$ paths of length $4$ which start and end at vertex $1$.

However, this is not what I get when I try to count the number of paths. The following is my approach:

• We need to start and end at vertex $1$. This means we need 3 vertices more to form the path.
• We can choose the second and third vertex in 4 ways each. While choosing the fourth vertex in the path, 2 cases arise:
  1. The third vertex is $1$: 4 ways to choose the fourth vertex.
  2. The third vertex is not $1$: 3 ways to choose the fourth vertex.
• However, in this method, symmetric paths (eg: $1 - 2 - 4 - 2 - 1$) have been counted twice, so we need to get rid of those. The number of ways to choose the second and third vertex is 4, and the number of ways to choose the third vertex is also 4. Therefore, total such symmetric paths are $4 * 4 = 16$.

From my calculation total number of paths of length $4$ that start and end at vertex $1$ are:

      $4*4 * (4 + 3) - 16 = 96$

---

What is the problem?

Clearly, the numbers from both approaches don't match. I don't believe that the method in the textbook is wrong as I have seen the same approach mentioned in many sources.

However, the text isn't very elaborate on what a path consists of, and therefore, I might be counting something more.

I have spent 2 days trying to figure this out but I do not seem to see where I am going wrong. I would love it if someone could help me out with this.

Answer 1

Here, you can define a path by a sequence of edges such that the terminal vertex of each edge in the path is equal to the starting vertex of the next (this ensures that successive vertices in the path cannot be the same).

The total number of paths is

$$4 \times (\underbrace{1\times 4}_{\substack{\text{Third vertex} \\ \text{is }1}} + \underbrace{3\times 3}_{\substack{\text{Third vertex} \\ \text{is not }1}}) = 52.$$

• The first term has a $1$ to show that the third vertex is fixed at $1$ and a $4$ to show that the fourth vertex can be any of the vertices other than $1$.
• The second term has a $3$ to show that the third vertex is anything other than $1$ and the second vertex, and the second $3$ to show that the fourth vertex is anything other than $1$ and the third vertex.

The symmetric paths are not being counted twice anywhere.