# Are isomorphic graphs also isospectral?

Two graphs are isomorphic if they just have a different labeling for their vertices i.e. if $A$ and $B$ are their adjacency matrices, then, for some permutation matrix $P$, $PAP^T = B$.

Two graphs are isospectral, if they have the same set of eigenvalues.

Question : Are isomorphic graphs necessarily isospectral?

## 3 Answers

The eigenvalues follow from the characteristic equation, so

\begin{align*} \det(B-\lambda I)&= \det(PAP^T-\lambda I)\\ &= \det(PAP^T-P(\lambda I) P^T)\\ &= \det(P(A-\lambda I)P^T)\\ &= \det(P)\det(A-\lambda I)\det(P^T)\\ &= \det(A-\lambda I) \end{align*}

so the two adjacency graphs have the same characteristic matrix and therefore the same eigenvalues. Note I used the fact that $PP^T=I$ and $\det(P)=\det(P^T)=1$

two isomorphic graphs are isospectral since they have the same number of cycles and nodes. quasi-isospectral graphs were also classified by Bisson and Tsemo by using closed models.

http://intlpress.com/site/pub/files/_fulltext/journals/hha/2009/0011/0001/HHA-2009-0011-0001-a008.pdf

Alternate proof in addition to the ones already mentioned :

Let $B = PAP^T$, then if $v$ was the eigenvector of $A$ corresponding to the eigenvalue $\lambda$ : $$B(Pv) = (PAP^T)(Pv) = PAv = \lambda Pv$$ Thus, $\lambda$ is also a eigenvalue of $B$.