Here is a seemingly easy exercise from Bondy and Murty’s book on graph theory:
For a simple graph $G$, show that the diagonal entries of $A^2$ are the degrees of the vertices of G.
Here, $A$ represents the adjacency matrix of the graph $G$. Although I have managed to come up with a proof that seems to be correct, I am dissatisfied because I do not know how to formulate it more rigorously . The verification that I came up with proceeds as follows:
First note that all entries of $A$ are either $0$ or $1$. Clearly, the diagonal entry $(i,i)$ of $A^2$ is given by:
($i$th row of $A$) $\cdot$ ($i$th column of $A$)
$=$ ($i$th row of $A$) $\cdot$ ($i$th row of $A$)
The previous line follows because $A$ is symmetric, i.e. $A=A^T$. Here, we have the dot product between two vectors.
Observe that all entries are either $0$ or $1$, and that the dot product of the $i$th row of $A$ with itself is equal to the sum of the squares of the entries in the row vector. Thus, we simply have that the dot product of the $i$th row of $A$ with itself is clearly equal to the sum of all the entries in the $i$th row of $A$, that is, the $i$th diagonal entry of $A^2$ is the degree of vertex $i$ in $G$.
However, is there a way to formulate this argument in a more mathematically concise manner?
Best Answer
Note that the $ij$ entry of $A^k$ counts the number of paths of length $k$ from $v_i$ to $v_j$
Thus if you have a vertex $v_i$ with degree k, that means you have $k$ paths of length $2$ from $v_i$ to itself, so $$ (A^2)_{ii} = k $$