Deux morceaux qu'aucune puissance ne relie

Les zéros persistants. Posons $P=\{1,2,3\}$ et $Q=\{4,5,6\}$. Aucune arête de la liste ne relie un sommet de $P$ à un sommet de $Q$ : les cinq arêtes sont soit entièrement dans $P$, soit entièrement dans $Q$.

Montrons par récurrence sur $d$ que $(A^d{)}_{ij}=0$ pour tout $i\in P$, $j\in Q$. Pour $d=1$ : $a_{ij}=0$, faute d'arête entre les paquets. Au rang $d+1$ : $$(A^{d+1}{)}_{ij}=\sum _{k=1}^6(A^d{)}_{ik}{a}_{kj}.$$ Si $k\in Q$, le facteur $(A^d{)}_{ik}$ est nul par hypothèse de récurrence ; si $k\in P$, le facteur $a_{kj}$ est nul faute d'arête entre les paquets. Chaque terme est donc nul, et la somme aussi — en particulier $(A^d{)}_{14}=0$ pour tout $d\ge 1$.

Le critère. La matrice $I_6+A+A^2+\cdots +A^5$ a pour coefficient $(1,4)$ la somme $0+0+\cdots +0=0$ (le terme venant de $I_6$ est nul puisque $1\ne 4$). Tous les coefficients ne sont donc pas strictement positifs : d'après le critère matriciel, $G$ n'est pas connexe.

Les composantes. Elles sont $P=\{1,2,3\}$ et $Q=\{4,5,6\}$ : le premier morceau est le triangle $1-2-3$, le second la chaîne $4-5-6$. Les zéros qui subsistent dans la somme des puissances désignent exactement les couples de sommets qu'aucune chaîne ne relie — le critère ne dit pas seulement « oui ou non », il donne le découpage.