Strong Graph Reconstruction Conjecture

For a graph $G$, its vertex deck is the multiset of graphs obtained by deleting one vertex. Bowler, Brown, and Fenner (BBF) proposed $2\lfloor\frac{n−1}{3}\rfloor$ as the maximum possible overlap between the decks of two nonisomorphic n-vertex graphs, for all sufficiently large n. We first give an explicit pair of connected nonisomorphic graphs on 78 vertices with at least 51 common cards, exceeding BBF's predicted value of 50. We then construct, for every even $r \geq 4$, families at arbitrarily large orders whose overlap fraction is asymptotically at least $1−\frac{1}{r}$. Consequently, for every $\alpha<1$, infinitely many pairs have more than $\alpha n$ common cards, so the attainable fraction is arbitrarily close to the full deck. For representative instances, the predicted overlaps were also checked by complete deck generation and isomorphism testing with Brendan McKay's nauty tools

Disproves the Bowler-Brown-Fenner bound of 2*floor((n-1)/3) on common cards between nonisomorphic graphs: an explicit connected 78-vertex pair shares at least 51 cards against the predicted 50, and for every even r >= 4 there are families with overlap fraction asymptotically at least 1 - 1/r, so the attainable fraction approaches the full deck. The Kelly-Ulam reconstruction conjecture itself is untouched.