Compter les chaînes par les puissances

Le graphe du cours a pour arêtes $\{1,2\}$, $\{1,5\}$, $\{2,3\}$, $\{3,4\}$, $\{4,5\}$ et $\{2,5\}$, d'où

$$A=\left(\begin{array}{ccccc}0& 1& 0& 0& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 1& 0\\ 0& 0& 1& 0& 1\\ 1& 1& 0& 1& 0\end{array}\right),A^2=\left(\begin{array}{ccccc}2& 1& 1& 1& 1\\ 1& 3& 0& 2& 1\\ 1& 0& 2& 0& 2\\ 1& 2& 0& 2& 0\\ 1& 1& 2& 0& 3\end{array}\right),A^3=\left(\begin{array}{ccccc}2& 4& 2& 2& 4\\ 4& 2& 5& 1& 6\\ 2& 5& 0& 4& 1\\ 2& 1& 4& 0& 5\\ 4& 6& 1& 5& 2\end{array}\right).$$

Le coefficient cherché est $(A^3{)}_{1,4}=2$.

Vérification par énumération. Les chaînes de longueur $3$ de $1$ à $4$ sont $1-2-3-4$ et $1-2-5-4$ : il y en a bien deux. On notera qu'aucune ne passe par $5$ en premier, car $5$ et $4$ sont voisins — $1-5-4-\cdots$ n'atteindrait pas $4$ en trois pas sans y revenir.

Deux lectures de $A^2$. Sa diagonale donne les degrés ($(A^2{)}_{ii}=\mathrm{deg}(i)$ : aller puis revenir) ; ses zéros signalent les paires de sommets sans voisin commun, comme $2$ et $3$.