Say $G$ and $H$ are two isomorphic graphs. There is the following theorem:
Two simple graphs $G$ and $H$ are isomorphic if and only if there exists a permutation matrix $P$ such that $A_G=PA_HP^t$.
But shouldn't this be a ''for all'' permutation matrices $P$ we have $A_G=PA_HP^t$?
It seems to me that every permutation matrix corresponds to a relabelling of the vertices of a graph. And it seems to me that any such relabelling will preserve all properties of the graph. Therefore, if $G$ and $H$ are isomorpphic then they still are isomorphic after any possible relabelling (permutation) of the vertices.
Why is this not so?
The adjacency matrix $A_G$ isn't solely a graph-theoretical property of $G$. The matrix $A_G$ is determined once we have picked
If we order the vertices differently, we get different adjacency matrices. This is where permutation matrices come in: if $P$ is a permutation matrix, then $P A_G P^{\mathsf T}$ gives us another adjacency matrix that comes from a different ordering.
Thus, even if $G$ and $H$ are isomorphic, we should not expect $A_G = A_H$, because to obtain $A_G$ and $A_H$, we picked an ordering of the vertices of $G$ and an ordering of the vertices of $H$. If $G$ and $H$ are isomorphic, and we chose compatible orderings of their vertices, then we should expect $A_G = A_H$.
If we did not choose compatible orderings, then the best we can say about isomorphic graphs $G,H$ is this: "Some adjacency matrix of $H$ is equal to $A_G$". The possible adjacency matrices of $H$ are given by $P A_H P^{\mathsf T}$ for various choices of $P$. Thus, we get the statement you quoted: $A_G = P A_H P^{\mathsf T}$ for some $H$.