Exercice 21 Compter les triangles

1. D'après la Proposition 2, le coefficient $(i\,;i)$ de $M^{3}$ est le nombre de chaînes de longueur $3$ partant de $i$ et revenant en $i$, c'est-à-dire de la forme $i$--$j$--$k$--$i$. Le graphe n'ayant pas de boucle, deux sommets consécutifs de cette liste sont distincts : $j\neq i$, $k\neq j$ et $k\neq i$. Les trois sommets $i$, $j$, $k$ sont donc distincts et deux à deux adjacents : ils forment un triangle.

2. Inversement, un triangle $\{i\,;j\,;k\}$ fournit exactement $6$ chaînes fermées de longueur $3$ : on peut partir de chacun des $3$ sommets, et tourner dans l'un des $2$ sens. Par exemple, pour un triangle $\{A\,;B\,;C\}$ : $A$--$B$--$C$--$A$, $A$--$C$--$B$--$A$, et de même depuis $B$ et depuis $C$. En sommant les coefficients diagonaux, on compte donc chaque triangle six fois : $$\boxed{\mathrm{trace}\left(M^{3}\right)=6\times(\text{nombre de triangles})}$$

3. Avec $M^{3}$ calculée à l'exercice 16 : $\mathrm{trace}\left(M^{3}\right)=2+4+4+2+0=12$, donc le graphe a $\frac{12}{6}=2$ triangles. Ce sont bien $\{A\,;B\,;C\}$ et $\{B\,;C\,;D\}$, que l'on voit sur la figure.

4. La matrice d'adjacence du graphe complet à $4$ sommets a des $1$ partout sauf sur la diagonale. La calculatrice donne : $$K=\begin{pmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} \qquad K^{3}=\begin{pmatrix} 6 & 7 & 7 & 7 \\ 7 & 6 & 7 & 7 \\ 7 & 7 & 6 & 7 \\ 7 & 7 & 7 & 6 \end{pmatrix}$$ $\mathrm{trace}\left(K^{3}\right)=24$, d'où $\boxed{4 \text{ triangles}}$. Directement : dans un graphe complet, trois sommets quelconques forment un triangle, et il y a $4$ façons de choisir $3$ sommets parmi $4$ (il suffit de choisir celui que l'on écarte).