Closed Walks, Traces, And Triangle Counts

From Walks to a Single Number

An adjacency-matrix power records many walk counts at once. Its diagonal entries focus on walks that return to their starting vertex, while the trace adds those counts over all possible starting vertices. For length three, the resulting total has a particularly simple interpretation: each triangle contributes six closed walks, one for each choice of starting vertex and direction.

Throughout, \(G=(V,E)\) is a finite simple undirected graph. A walk of length \(k\) is a sequence \(v_0,v_1,\dots,v_k\) in which consecutive vertices are adjacent; vertices and edges may repeat. It is closed if \(v_k=v_0\). A triangle is a set of three distinct vertices with all three edges between them.

Since the graph is simple and undirected, \(\mathbf A\) is symmetric and has zero diagonal. The ordering of vertices affects how the matrix is displayed, but not the walk counts or trace formulas below.

Diagonal Entries and Closed Walks

Proof. For \(k=0\), \(\mathbf A^0\) is the identity matrix: its \(ij\) entry is \(1\) if \(i=j\) and \(0\) otherwise. This agrees with the number of length-zero walks from \(v_i\) to \(v_j\), since such a walk stays at its one starting vertex. Now suppose the claim holds for \(k\). Matrix multiplication gives \((\mathbf A^{k+1})_{ij}=\sum_{\ell=1}^n(\mathbf A^k)_{i\ell}A_{\ell j}\). For each \(\ell\), the first factor counts walks of length \(k\) from \(v_i\) to \(v_\ell\), and the second factor is \(1\) exactly when \(v_\ell v_j\) is an edge. Thus the sum counts exactly the walks formed by taking a length-\(k\) walk to \(v_\ell\) and then the final edge to \(v_j\). This proves the claim by induction. Setting \(i=j\) gives the closed-walk interpretation of the diagonal, and summing those entries gives the trace interpretation. \(\square\)

This result counts walks, not paths: a walk is allowed to repeat a vertex or edge. For instance, a walk of length two can travel along an edge and immediately return along the same edge. The zero diagonal of \(\mathbf A\) means there are no length-one closed walks in a simple graph; the length-zero case is different, since each vertex has one length-zero walk starting and ending there.

Proof. A length-two walk from \(v_i\) back to itself chooses a neighbor \(v_j\) of \(v_i\), then returns along the same edge. There is exactly one such walk for each neighbor, so the diagonal entry is \(\deg(v_i)\). Summing gives \(\operatorname{tr}(\mathbf A^2)=\sum_{v\in V}\deg(v)\). Each edge contributes one to the degree of each of its two endpoints, so this sum is \(2|E|\). \(\square\)

Why the Cube Counts Triangles

The trace of \(\mathbf A^3\) counts all closed walks of length three, with a walk counted separately for every starting vertex and order in which it is traversed. In a simple graph, each such walk must use three distinct vertices: if two consecutive vertices in the three-step closed sequence were equal, one of its steps would be a loop, which is not allowed. If the first and third vertices were equal, the final step back to the starting vertex would be a loop. Therefore the three vertices are distinct, and all three edges between them are present. They form a triangle.

Proof. By the proposition, the trace counts every closed walk of length three. The preceding argument shows that every such walk visits three distinct vertices and therefore traverses a triangle. Conversely, each triangle with vertices \(a,b,c\) gives exactly six closed walks of length three: there are three choices for the starting vertex, and from each starting vertex there are two directions around the triangle. These six walks are distinct as sequences of vertices. Also, a closed walk determines its three vertices and hence determines its triangle, so walks arising from different triangles are not counted together. Thus each triangle contributes exactly six to the trace, and no other closed walks contribute. Therefore \(\operatorname{tr}(\mathbf A^3)=6T(G)\). \(\square\)

A useful way to compute the diagonal entries of \(\mathbf A^3\) is to first calculate \(\mathbf A^2\). The multiplication rule gives \((\mathbf A^3)_{ii}=\sum_j(\mathbf A^2)_{ij}A_{ji}\), so only neighbors \(v_j\) of \(v_i\) contribute. In a simple undirected graph, \((\mathbf A^2)_{ij}\) counts the common neighbors of \(v_i\) and \(v_j\): a length-two walk from \(v_i\) to \(v_j\) chooses exactly such a common neighbor. This makes the trace calculation particularly concrete.

Common Counting Pitfall

Do not divide the trace by three. In the \(K_3\) example, the trace is 6, and dividing by 3 would give 2, although there is only one triangle. The trace counts walks with both a starting vertex and a direction specified. Each triangle has three choices of starting vertex and two choices of direction, so the correct divisor is \(3\cdot2=6\).

There is a related but different count using common neighbors. If one sums the number of common neighbors over all edges, each triangle is counted once for each of its three edges. That sum is therefore three times the number of triangles. It has a different divisor because it counts edge-triangle incidences, not rooted, directed closed walks. Keeping track of exactly what is being counted is essential whenever a matrix sum is translated into a graph count.

The trace is useful because it compresses a count over all starting vertices into one matrix quantity. For length two it recovers twice the number of edges; for length three it recovers six times the number of triangles. The same walk-counting interpretation applies to other powers, although longer closed walks can revisit vertices and edges, so their traces generally count more varied configurations than triangles.