I'm a chemist, not mathematician. I learned graph theory just to supplement my knowledge on chemical graph theory and a bit of computer science. I have some question related to spectrum of a graph.
- How do we prove that spectrum of a graph is invariant? because to be honest, the best way I can think of is by using definition of determinant and Levi-Civita symbol. Can someone please tell me how to prove it, or provide a reference to the proof?
- In Wikipedia I read
While the adjacency matrix depends on the vertex labeling, its spectrum is a graph invariant, although not a complete one.
What does it mean by that?
Is it perhaps because spectrum of some graph (like multigraph) is not an invariant? How do we prove that?
If adjacent matrix of graph $G$ is $A_1$ and $A_2$ for labeling $I_1=\{i_1,i_2,\dots,i_n\}$ and $I_2=\{i^\prime_1,i^\prime _2,\dots,i^\prime_n \}$ respectively. then $A_1$ and $A_2$ are permutation-similar matrices, meaning there is a permutation matrix $P$ ($PP^t=\mathbb{I}_n$) which $A_1 = P A_2 P^t$. eigenvalues and degeneracy degree (multiplicity) of them are invariant under this transformation: $$ \det(\lambda \mathbb{I}-A_1)= \det(\lambda \mathbb{I}-P A_2 P^t)= \\ \det(P(\lambda \mathbb{I}-A_2) P^t) = \det(PP^t)\det(\lambda \mathbb{I}-A_2)=\det(\lambda \mathbb{I}-A_2) $$ so eigenvalues of $A_1$ are also eigenvalues of $A_2$. and because charactrisctic polynomial of both matrices are equal ($\det(x \mathbb{I}-A_1)$), multiplicity of eigenvalues are also same. so spectral of graph for both of these matrix representations are equal. hence spectral of graph is invariant under relabeling the graph.
This calculations are valid for isomorphic graph for exacty same reason. so the spectrum is a graph invariant.