From Walk Counts to Connectivity
An adjacency matrix records which pairs of vertices are joined by an edge. Its powers record more: the entry in row \(u\), column \(v\) of the \(k\)th power counts walks of length \(k\) from \(u\) to \(v\). Since connectivity asks whether there is a path between two vertices, this count gives a direct test: the vertices are connected exactly when at least one of the relevant powers has a positive entry in that position.
Throughout, graphs are finite and simple. A walk of length \(k\) from \(u\) to \(v\) is a sequence \(v_0,v_1,\ldots,v_k\) with \(v_0=u\), \(v_k=v\), and consecutive vertices adjacent. A path is a walk with no repeated vertices. Two vertices are connected if there is a path between them. Every walk from \(u\) to \(v\) contains a path from \(u\) to \(v\): whenever a vertex repeats, delete the portion of the walk between two occurrences of that vertex; repeating this deletion shortens the walk until no vertex repeats.
Fix an ordering \(V(G)=\{v_1,\ldots,v_n\}\). The adjacency matrix \(\mathbf A=\mathbf A(G)\) has entry \(1\) in position \((i,j)\) if \(v_iv_j\in E(G)\), and entry \(0\) otherwise. Because the graph is simple, its diagonal entries are \(0\). We use \(\mathbf A^0=\mathbf I\), the identity matrix. Thus the zeroth power records length-zero walks: its \((u,v)\) entry is \(1\) if \(u=v\), and \(0\) otherwise.
Proof. We use induction on \(k\). For \(k=0\), the identity matrix has entry \(1\) precisely when \(u=v\), which is exactly the number of length-zero walks from \(u\) to \(v\). Suppose the statement holds for \(k\). Matrix multiplication gives \((\mathbf A^{k+1})_{uv}=\sum_{w\in V(G)}(\mathbf A^k)_{uw}\mathbf A_{wv}\). For each \(w\), the first factor counts length-\(k\) walks from \(u\) to \(w\), and the second factor is \(1\) precisely when \(wv\) is an edge. Therefore that product counts the length-\((k+1)\) walks from \(u\) to \(v\) whose penultimate vertex is \(w\). Each length-\((k+1)\) walk has exactly one penultimate vertex, so summing over \(w\) counts every such walk exactly once. This proves the induction step and the theorem. \(\square\)
The Connectivity Criterion
Proof. First suppose \((\mathbf A^k)_{uv}>0\) for some \(k\) in the stated range. By the walk-count theorem, there is a walk from \(u\) to \(v\). Deleting portions between repeated vertices, as described above, gives a path from \(u\) to \(v\). Thus the vertices are connected.
Conversely, suppose \(u\) and \(v\) are connected. If \(u=v\), then \((\mathbf A^0)_{uu}=1>0\). If \(u\ne v\), take a path from \(u\) to \(v\). A path has no repeated vertices, so it uses at most the \(n\) vertices of \(G\), and its length \(k\) is at most \(n-1\). Its length is positive because its endpoints differ. The walk-count theorem then gives \((\mathbf A^k)_{uv}\geq 1\). Both implications hold, proving the criterion. \(\square\)
The bound \(n-1\) is useful because it turns the criterion into a finite test. For a graph with \(n\geq1\), define \(\mathbf S=\mathbf A^0+\mathbf A^1+\cdots+\mathbf A^{n-1}\). All summands have nonnegative entries, so \(\mathbf S_{uv}>0\) exactly when at least one of those powers has a positive \((u,v)\) entry. The theorem shows that this is exactly when \(u\) and \(v\) are connected. In particular, the vertices with positive entries in a given row of \(\mathbf S\) are precisely the vertices in the same component as that row’s vertex.
If \(n=0\), there are no vertices or vertex pairs to test, and the graph has no components. If \(n=1\), the test uses only \(\mathbf A^0=\mathbf I\); the single vertex is connected to itself, whether or not it has any incident edges. More generally, the identity term ensures that every vertex is counted as belonging to its own component, including an isolated vertex.
Using the Sum of Powers
Worked Example: A Path Component and a Single Edge
Let \(G\) have ordered vertex set \(\{1,2,3,4,5\}\) and edge set \(\{12,23,45\}\). Thus one component is the path \(1,2,3\), and the other is the single edge \(45\). Since \(n=5\), compute \(\mathbf S=\sum_{k=0}^{4}\mathbf A^k\). The adjacency matrix has blocks for the two components and is \(\mathbf A=\begin{pmatrix}0&1&0&0&0\\1&0&1&0&0\\0&1&0&0&0\\0&0&0&0&1\\0&0&0&1&0\end{pmatrix}\).
On vertices \(1,2,3\), write the adjacency block as \(\mathbf B\). Direct multiplication gives \(\mathbf B^2=\begin{pmatrix}1&0&1\\0&2&0\\1&0&1\end{pmatrix}\), \(\mathbf B^3=2\mathbf B\), and \(\mathbf B^4=2\mathbf B^2\). Hence \(\mathbf I+\mathbf B+\mathbf B^2+\mathbf B^3+\mathbf B^4=\mathbf I+3\mathbf B+3\mathbf B^2 =\begin{pmatrix}4&3&3\\3&7&3\\3&3&4\end{pmatrix}\). For the edge \(45\), its adjacency block \(\mathbf C=\begin{pmatrix}0&1\\1&0\end{pmatrix}\) satisfies \(\mathbf C^2=\mathbf I\), so \(\mathbf C^0+\mathbf C^1+\mathbf C^2+\mathbf C^3+\mathbf C^4=3\mathbf I+2\mathbf C=\begin{pmatrix}3&2\\2&3\end{pmatrix}\).
There are no edges between the two components, so every power has zero entries between their vertex sets. Combining the blocks gives \(\mathbf S=\begin{pmatrix}4&3&3&0&0\\3&7&3&0&0\\3&3&4&0&0\\0&0&0&3&2\\0&0&0&2&3\end{pmatrix}\). The positive entries identify exactly the two components: \(\{1,2,3\}\) and \(\{4,5\}\).
Check: The first block has positive entries in all nine positions, matching the fact that every pair among \(1,2,3\) is joined by a path. In the second block, the off-diagonal entries are \(2\), obtained from the two length-one and length-three walks along the edge; its diagonal entries are \(3\), obtained from lengths zero, two and four. The cross-block entries are zero because a walk cannot pass between the two vertex sets.
Worked Example: A Positive Entry Beyond the Adjacency Matrix
Let \(G\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34\}\), so \(G=P_4\). In the vertex order \(1,2,3,4\), \(\mathbf A=\begin{pmatrix}0&1&0&0\\1&0&1&0\\0&1&0&1\\0&0&1&0\end{pmatrix}\). Squaring and then multiplying once more gives \(\mathbf A^2=\begin{pmatrix}1&0&1&0\\0&2&0&1\\1&0&2&0\\0&1&0&1\end{pmatrix}\) and \(\mathbf A^3=\begin{pmatrix}0&2&0&1\\2&0&3&0\\0&3&0&2\\1&0&2&0\end{pmatrix}\).
For example, the \((1,3)\) entry of \(\mathbf A\) is \(0\), since \(1\) and \(3\) are not adjacent. But \((\mathbf A^2)_{13}=1\), counting the walk \(1,2,3\). Likewise, the \((1,4)\) entry of \(\mathbf A^3\) is \(1\), counting \(1,2,3,4\). All four vertices are therefore in one component.
Check: Adding the displayed powers to \(\mathbf A^0=\mathbf I\) gives \(\mathbf S=\mathbf I+\mathbf A+\mathbf A^2+\mathbf A^3 =\begin{pmatrix}2&3&1&1\\3&3&4&1\\1&4&3&3\\1&1&3&2\end{pmatrix}\). Every entry is positive, in agreement with the paths along \(P_4\). For instance, the \((1,4)\) entry is \(0+0+0+1=1\), so the length-three path is counted once in the sum.
Worked Example: Leaves Connected Through a Centre
Let \(G\) have vertex set \(\{1,2,3,4\}\) and edge set \(\{12,13,14\}\), the star with centre \(1\). Its adjacency matrix is \(\mathbf A=\begin{pmatrix}0&1&1&1\\1&0&0&0\\1&0&0&0\\1&0&0&0\end{pmatrix}\). Multiplying gives \(\mathbf A^2=\begin{pmatrix}3&0&0&0\\0&1&1&1\\0&1&1&1\\0&1&1&1\end{pmatrix}\). The entries \((\mathbf A^2)_{23}\), \((\mathbf A^2)_{24}\), and \((\mathbf A^2)_{34}\) all equal \(1\): for example, the one length-two walk from \(2\) to \(3\) is \(2,1,3\). Thus the leaves are connected even though no two leaves are adjacent.
Check: The centre is adjacent to each leaf, so its three corresponding entries in \(\mathbf A\) are \(1\). Each pair of distinct leaves has a length-two walk through \(1\), so its corresponding entry in \(\mathbf A^2\) is \(1\). These paths connect every pair of vertices, confirming that the graph has one component.
Why the Criterion Works—and a Common Mistake
Connectivity is a question about the existence of a route, not about direct adjacency. The adjacency matrix alone answers only the length-one question. Higher powers test longer walks; a positive entry is enough because a walk always contains a path with the same endpoints. Conversely, any path in an \(n\)-vertex graph has length at most \(n-1\), which is why powers beyond \(n-1\) are unnecessary for deciding which vertices are connected.
Common mistake: treating a zero entry of \(\mathbf A\) as evidence of disconnection. In the \(P_4\) example, \(\mathbf A_{13}=0\). Concluding that vertices \(1\) and \(3\) lie in different components would be wrong: the length-two walk \(1,2,3\) gives \((\mathbf A^2)_{13}=1\), and the vertices are connected. The correction is to test whether some power has a positive entry, or equivalently whether their entry in \(\mathbf S\) is positive. Also, a zero entry in one particular power says only that there is no walk of that particular length; it does not rule out a walk of another length.
The finite-sum test does not require a graph to be connected in advance. Applying it to every pair partitions the vertices into components, with isolated vertices appearing as singleton components. For practical calculations, one can stop testing a pair as soon as a positive entry is found; to certify that two vertices are in different components, all powers through \(n-1\) must have zero in their position.
Check Your Understanding
Use the walk-count interpretation and the connectivity criterion to justify each answer.
- For a graph on \(8\) vertices, what is the largest power that needs to be tested for two distinct vertices?
- In the graph with vertex set \(\{a,b,c,d\}\) and edge set \(\{ab,bc,cd\}\), why does a positive \((\mathbf A^3)_{ad}\) entry establish that \(a\) and \(d\) are connected?
- What does \((\mathbf A^0)_{vv}\) equal, and why is this useful when \(v\) is isolated?
- Can \((\mathbf A^2)_{uv}=0\) imply that distinct vertices \(u,v\) are disconnected? Explain.
- For the star in the final worked example, which power first has a positive entry between two distinct leaves?