Renuméroter les sommets

La première matrice. Le sommet $1$ est relié à $2$ seulement, le sommet $2$ à $1$ et $3$, le sommet $3$ à $2$ seulement : $$A=\left(\begin{array}{ccc}0& 1& 0\\ 1& 0& 1\\ 0& 1& 0\end{array}\right).$$

Après échange. Ce qui portait le numéro $1$ porte maintenant le numéro $2$, et réciproquement ; le sommet $3$ ne change pas. Les arêtes, elles, ne bougent pas : $\{1,2\}$ reste la même paire, et $\{2,3\}$ devient $\{1,3\}$. D'où $$A^{\prime }=\left(\begin{array}{ccc}0& 1& 1\\ 1& 0& 0\\ 1& 0& 0\end{array}\right).$$

Comparaison. $A\ne A^{\prime }$ : les deux matrices n'ont pas les mêmes coefficients ($a_{13}=0$ mais $a_{13}^{\prime }=1$). Pourtant elles décrivent le même graphe, à une renumérotation près.

En revanche :

• la liste des degrés est la même à l'ordre près — $(1,2,1)$ pour $A$, $(2,1,1)$ pour $A^{\prime }$ : ce sont les mêmes valeurs, portées par d'autres numéros ;
• le nombre d'arêtes est le même, $m=2$, ce que confirme la formule d'Euler ($1+2+1=4=2\times 2$ dans les deux cas).

Conclusion. La matrice d'adjacence dépend de la numérotation choisie, qui est un choix arbitraire ; le graphe, lui, n'en dépend pas. Toute quantité que l'on veut attribuer au graphe doit donc être invariante par renumérotation : c'est le cas du nombre d'arêtes, de la liste des degrés, du caractère connexe, mais pas du coefficient $a_{13}$ pris isolément.