Démontrer le nombre de chemins de longueur n avec la matrice d'adjacence - Exercice 3

Finalement :
D'après la calculatrice, on obtient :
$$M^{3}=\left(\begin{array}{cccccc} {2} & {5} & {6} & {3} & {3} & {3} \\ {5} & {4} & {7} & {8} & {4} & {3} \\ {6} & {7} & {6} & {9} & {8} & {3} \\ {3} & {8} & {9} & {6} & {7} & {6} \\ {3} & {4} & {8} & {7} & {4} & {5} \\ {3} & {3} & {3} & {6} & {5} & {2} \end{array}\right)$$

Ce coefficient est le nombre de chemins de longueur $$3$$ allant de $$i$$ à $$i$$ . Un tel chemin s'écrit $$i-j-k-i$$ : comme il n'y a pas de boucle, $$j\ne i$$ , $$k\ne j$$ et $$k\ne i$$ ; les trois sommets $$i$$ , $$j$$ et $$k$$ sont distincts et adjacents deux à deux, ils forment un triangle.
Inversement, chaque triangle $$\left\{i;j;k\right\}$$ donne exactement deux chemins de longueur $$3$$ allant de $$i$$ à $$i$$ : $$i-j-k-i$$ et $$i-k-j-i$$ .
Ainsi :

La somme des coefficients diagonaux de $$M^{3}$$ est égale à $$2+4+6+6+4+2=24$$ .
D'après la question $$2$$ , chaque triangle y est compté deux fois pour chacun de ses trois sommets, c'est-à-dire $$6$$ fois. Le nombre de triangles est donc $$\dfrac{24}{6}=4$$ .
Finalement :