The simple connected graph $G$ has $n$ vertices and we have:


1) $|E(G)|‎\geq‎ \frac{n(n-1)}{3}$


2) we have the spectrum and degree sequence of $G$


3) $Spectrum(G)=Spectrum(H)$


Is $G \cong ‎H$?



cospectral graphs
No. $H$ is isomorphic to $G$ if and only if the same is true of their complements. The complements of $G$ and $H$ are required to be mildly sparse graphs (certainly $k$-regular for any $k$ is fine, as long as $n$ is reasonably large), and one can certainly find $k$ regular isospectral non-isomorphic graphs.


**EDIT** To find such families, google "isospectral cubic graphs". Some of the things which come up are NOT cubic (e.g., the paper Isospectral Cayley graphs of some finite simple groups by Lubotzky, Samuels, Vishne gets examples for almost all degrees.)


