There's a graph $G$ which is conjectured to exist. We know it's $k$-regular, and we know its spectrum. (I don't think the exact problem is important for this question). $G$ is much too large to attack directly by computation, however, some time ago I was able to produce (with computer assistance) a graph $H$ such that if $G$ exists, then $H$ must be a subgraph of $H$.
$H$ is very much not induced. $H$ has as many vertices as $G$, and is connected, but it only has about %7 of the edges that $G$ does. This may not sound promising but for about 100 vertices (3% of the total) of $H$, they have degree $k$ (the regularity of $G$). Almost all the other vertices of $H$ have degree 2.
So, in terms of edges $H$ is a far cry from being all of $G$, but there's a handful of vertices that have all their neighbors.
Question Set One: Is there any hope we can use $H$ and our knowledge of the spectrum to reconstruct $G$? If not all of $G$, can we at least use our knowledge of the spectrum to add some more edges to $H$? If there's any textbooks or papers that deal with something similar, please share them below.
Also, my construction of $H$ begins by imagining a single vertex of $G$ "building out" from there. Let's call this vertex $v$, thinking of it as a sort of "root" for the construction of $H$. This means that, while $G$ is known to not be vertex-transitive, we know that for any vertex $u$ of $G$, we can embed $H$ into $G$ in such a way that $v$ gets sent to $u$. (Of course we have no idea how any two such embeddings of $H$ interact/which vertices should correspond to each other)
Question Two: Could the information in the above paragraph be useful adding more edges to $H$, either on its own or in tandem with the first question?
My own work is far away from graph theory, so I'm happy to hear about any theorems, texts, or people that seem at least vaguely related to this plan of attack.