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⌊(n−1)/3⌋ 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≥4, families at arbitrarily large orders whose overlap fraction is asymptotically at least 1−1/r. Consequently, for every α<1, infinitely many pairs have more than α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