Connexe ou non ?

Le premier graphe n'est pas connexe. Il faut exhiber deux sommets qu'aucune chaîne ne relie. Prenons $1$ et $3$. Une chaîne partant de $1$ ne peut emprunter que l'arête $\{1,2\}$, et arrive donc en $2$ ; depuis $2$, la seule arête disponible est encore $\{1,2\}$, qui ramène en $1$. Toute chaîne issue de $1$ reste donc dans $\{1,2\}$ et n'atteint jamais $3$.

Le graphe est fait de deux morceaux : $\{1,2\}$ et $\{3,4\}$.

Le second graphe est connexe. Il faut cette fois exhiber une chaîne pour chaque couple de sommets. La chaîne $1-2-3-4$ passe par les quatre sommets : elle relie $1$ à $2$, à $3$ et à $4$, et l'on en extrait une chaîne entre deux sommets quelconques (par exemple $2-3-4$ pour le couple $(2,4)$). Tout couple est donc relié : le graphe est connexe.

Par le critère matriciel. Pour le premier graphe, $A=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right)$ : les coefficients $(1,3)$ de $A$, $A^2$, $A^3$ sont tous nuls, donc celui de $I_4+A+A^2+A^3$ aussi, et le critère conclut à la non-connexité. Pour le second, il faudrait aller jusqu'à $A^3$ pour relier $1$ à $4$ — c'est le sens de la borne $n-1=3$ du théorème : s'arrêter à $A^2$ conclurait, à tort, que le graphe n'est pas connexe.