A computer stores a graph as a table of zeros and ones. That table, a matrix, does more than store: matrix multiplication turns out to count routes through the graph. This uses the walks from connectivity and the named graphs from special graphs.
Key idea
For a graph with vertices $1, \ldots, n$, the adjacency matrix $A$ has entry $A_{ij} = 1$ when $i$ and $j$ are joined and $0$ otherwise. It is symmetric, its diagonal is $0$, and row $i$ adds up to $\deg(i)$. The $(i, j)$ entry of $A^{k}$ is the number of walks of length $k$ from $i$ to $j$.
Why it works
Look at $A^{2}$: $(A^{2})_{ij} = \sum_{m} A_{im}A_{mj}$. A term is $1$ exactly when $m$ is joined to both $i$ and $j$, that is, when $i \to m \to j$ is a walk of length $2$. So the sum counts those walks, one per middle vertex. The same idea extends: $(A^{k+1})_{ij} = \sum_{m} (A^{k})_{im}A_{mj}$ counts walks of length $k$ from $i$ to some $m$, followed by one more step to $j$, and induction gives the result for every $k$.
Worked examples
Worked example: Reading a matrix
Vertices $1, 2, 3, 4$ have $$A = \begin{bmatrix} 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 \end{bmatrix}.$$ Find the degree of vertex $2$, the number of edges, and the number of walks of length $2$ from $1$ to $4$.
- Row $2$ adds to $3$: degree $3$.
- All entries add to $10$; each edge appears twice, so there are $5$ edges.
- $(A^{2})_{14}$ = row $1$ times column $4$: $0 \cdot 0 + 1 \cdot 1 + 1 \cdot 1 + 0 \cdot 0 = 2$. The walks are $1 \to 2 \to 4$ and $1 \to 3 \to 4$.
Answer: degree $3$; $5$ edges; $2$ walks
Worked example: The diagonal of $A^{2}$
Why is $(A^{2})_{ii} = \deg(i)$?
- A walk of length $2$ from $i$ back to $i$ goes out along an edge and comes back along the same edge.
- There is one such walk for each neighbor of $i$, so their number is $\deg(i)$.
Answer: Each neighbor gives one out-and-back walk.
Worked example: Counting triangles
Explain why the number of triangles is $\frac{1}{6}$ of the sum of the diagonal entries of $A^{3}$.
- A diagonal entry $(A^{3})_{ii}$ counts closed walks of length $3$ from $i$; in a simple graph each one goes around a triangle.
- One triangle $\{a, b, c\}$ produces $6$ such walks: $3$ starting points times $2$ directions.
- So the diagonal sum is $6$ times the number of triangles.
Answer: Each triangle is counted $6$ times.
Common mistake
Thinking $A^{k}$ counts paths. The walks it counts may repeat vertices and edges: in the first example, $(A^{2})_{11} = 2$ counts $1 \to 2 \to 1$ and $1 \to 3 \to 1$, which go back and forth along one edge. Check: list a few of the walks behind an entry; if some repeat a vertex, the entry is counting walks, as it always does.