Recovering Degrees And Neighborhoods From Adjacency Matrices

Reading Degrees and Neighborhoods from Rows

An adjacency matrix records which pairs of vertices are joined by edges. Once the vertices have been assigned an order, each row records the connections of one vertex: the positions of its nonzero entries identify its neighbors, and the number of those entries gives its degree. These facts turn basic graph information into direct matrix calculations.

Throughout, \(G=(V,E)\) is a finite simple undirected graph, with no loops or multiple edges. Fix an ordering \(V=\{v_1,\dots,v_n\}\). Its adjacency matrix is the \(n\) by \(n\) matrix \(A=(a_{ij})\) defined by \(a_{ij}=1\) when \(v_i v_j\in E\), and \(a_{ij}=0\) otherwise. Since the graph is undirected, \(a_{ij}=a_{ji}\); since it has no loops, \(a_{ii}=0\).

There are two details to keep in mind. First, a support is a set of column positions, not a set of matrix-entry values: the value \(1\) tells us that a neighbor is present, while the column index tells us which vertex it is. Second, the entries are added as ordinary integers. The degree counts incident edges, so it is the number of \(1\)s in the row.

Proof. By definition, \(a_{ij}=1\) exactly when \(v_j\) is adjacent to \(v_i\), and is \(0\) otherwise. Thus the indices of the nonzero entries in row \(i\) are exactly the vertices in \(N(v_i)\). Each such entry contributes \(1\) to the row sum, and all other entries contribute \(0\). Therefore the row sum is the number of vertices adjacent to \(v_i\), which is \(\deg(v_i)\) in a simple graph. \(\square\)

Equivalently, if \(\mathbf{1}\) is the column vector of \(n\) ones, then \(A\mathbf{1}\) is the column vector of vertex degrees: its \(i\)th entry is the sum of row \(i\). This gives a compact way to check all degrees at once.

Worked Examples

Regularity as a Row-Sum Test

Proof. Suppose first that \(G\) is \(r\)-regular. Then every vertex \(v_i\) has degree \(r\), and the row-sum proposition shows that row \(i\) sums to \(r\). This holds for every row, so \(A\mathbf{1}=r\mathbf{1}\). Conversely, suppose every row sums to \(r\). By the same proposition, \(\deg(v_i)=r\) for every vertex \(v_i\). Hence all vertices have the same degree, so \(G\) is \(r\)-regular. The argument also covers the graph with no vertices: it has no rows, and the condition that every row sum equals \(r\) is vacuously true for each \(r\); the equation \(A\mathbf{1}=r\mathbf{1}\) uses empty vectors and holds vacuously. \(\square\)

For a nonempty graph, the row sums give a direct test: compute them all and compare. If even two row sums differ, the graph is not regular. If they all agree, their common value is the degree of every vertex. The first example is \(2\)-regular; the second and third examples are not regular because their row sums are unequal.

Since the graph is undirected, \(A\) is symmetric, so column \(i\) also records the neighbors of \(v_i\). In particular, its column sum equals its row sum. For degree and neighborhood calculations, however, one row per vertex is enough; use the column positions to name the neighbors.

Common Mistakes and a Reliable Check

A frequent mistake is to treat the values in a row as vertex labels. For instance, in the graph \(V=\{1,2,3,4\}\), \(E=\{12,23,34\}\), the row for vertex \(2\) is \((1,0,1,0)\). Taking the set of distinct nonzero values gives \(\{1\}\), which is not the neighborhood. The nonzero entries occur in columns 1 and 3, so the correct result is \(N(2)=\{1,3\}\), and the row sum \(1+0+1+0=2\) gives degree \(2\).

Another error is to infer regularity from one row, or from a few selected rows. Regularity requires that every vertex have the same degree, so every row must be checked. In the second example, three rows have sums \(2,2,3\) before the fourth row, whose sum is \(1\); checking only the first two rows would miss the failure of regularity.

A useful consistency check is to add all row sums and compare with twice the number of edges. Each edge \(v_i v_j\) contributes a \(1\) in row \(i\), column \(j\), and a \(1\) in row \(j\), column \(i\). It therefore contributes exactly \(2\) to the sum of all entries. Thus the total of the degrees must equal \(2|E|\). This check can expose an arithmetic error, but it does not replace checking the individual rows when determining neighborhoods or regularity.