Compter des chaînes de longueur deux

La règle. Une chaîne de longueur $2$ de $i$ à $j$ est le choix d'un sommet intermédiaire $k$ relié à la fois à $i$ et à $j$. Il suffit donc de compter les voisins communs.

Les listes de voisins. $$N(1)=\{2,3\},N(2)=\{1,3,4\},N(3)=\{1,2\},N(4)=\{2\}.$$

De $1$ à $4$. $N(1)\cap N(4)=\{2,3\}\cap \{2\}=\{2\}$ : un seul sommet intermédiaire, donc une chaîne de longueur $2$, à savoir $$1-2-4.$$

De $3$ à $4$. $N(3)\cap N(4)=\{1,2\}\cap \{2\}=\{2\}$ : là encore une seule chaîne, $$3-2-4.$$

Le lien avec la matrice. La matrice d'adjacence est $$A=\left(\begin{array}{cccc}0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 0\\ 0& 1& 0& 0\end{array}\right),$$ et le théorème des puissances affirme que $(A^2{)}_{14}$ et $(A^2{)}_{34}$ comptent ces chaînes. Le calcul donne bien $(A^2{)}_{14}=0\times 0+1\times 1+1\times 0+0\times 0=1$ et $(A^2{)}_{34}=0\times 0+1\times 1+0+0=1$, en accord avec l'énumération.

Attention : le sommet $4$ n'a qu'un voisin, ce qui limite fortement les chaînes qui y aboutissent. Un sommet de degré $1$ ne peut être atteint que par l'unique arête qui y mène.