Les voisins communs se lisent sur $A^2$

La démonstration. Par définition du produit matriciel, $$(A^2{)}_{ij}=\sum _{k=1}^n{a}_{ik}{a}_{kj}.$$ Chaque terme $a_{ik}{a}_{kj}$ vaut $1$ si $k$ est voisin de $i$ et voisin de $j$, et $0$ sinon : c'est un produit de deux nombres valant $0$ ou $1$. La somme compte donc exactement les sommets $k$ adjacents aux deux. Pour $i\ne j$ et un graphe sans boucle, aucun de ces $k$ ne peut valoir $i$ ni $j$ (il faudrait $a_{ii}=1$), et l'interprétation est complète.

C'est aussi le théorème des puissances lu autrement : une chaîne de longueur $2$ de $i$ à $j$ est le choix d'un sommet intermédiaire adjacent aux deux.

Le graphe de l'énoncé. Les listes de voisins se lisent sur les arêtes : $$N(1)=\{2,3\},N(2)=\{1,3,4\},N(3)=\{1,2,5\},N(4)=\{2,5\},N(5)=\{3,4\}.$$ Contrôle : les degrés sont $2,3,3,2,2$, de somme $12=2\times 6$, et il y a bien $6$ arêtes.

Sommets $1$ et $4$. $N(1)\cap N(4)=\{2,3\}\cap \{2,5\}=\{2\}$ : un seul voisin commun, donc $(A^2{)}_{14}=1$. La seule chaîne de longueur $2$ est $1-2-4$.

Sommets $2$ et $5$. $N(2)\cap N(5)=\{1,3,4\}\cap \{3,4\}=\{3,4\}$ : deux voisins communs, donc $(A^2{)}_{25}=2$, correspondant aux chaînes $2-3-5$ et $2-4-5$.

Sur la diagonale, en revanche, $(A^2{)}_{ii}={\sum }_k{a}_{ik}^2=\mathrm{deg}(i)$ : la lecture « voisins communs » ne vaut que hors diagonale.