I don't think that follows. Since the adjacency matrix contains O(n^2) _bits_ of information, the number of adjacency matrices of graphs is O(2^(n^2)). This mak

I don't think that follows. Since the adjacency matrix contains O(n^2) _bits_ of information, the number of adjacency matrices of graphs is O(2^(n^2)). This makes sense: graphs with vertex labels {1,...,n} are in bijection with symmetric n x n binary matrices with zero diagonal. It's difficult to quantify how much information is lost when we reduce this matrix to its spectrum, since the eigenvalues are real numbers, but there are O(n) degrees of freedom, and in principle plenty of room to distinguish any two graphs. Of course, as a sibling comment notes, unlabeled graphs are often more interesting, for which one has to look at equivalence classes of adjacency matrices. The spectrum is nice here because it is automatically invariant to vertex permutations and hence a graph isomorphism invariant. The existence of nonisomorphic cospectral graphs is not immediately obvious, although there are simple examples, and that there are infinite families of cospectral pairs is even less obvious. So at the very least, it's interesting that the spectrum is not a complete invariant, and that it does work well for certain classes of graphs.