Strong Graph Reconstruction Conjecture
Statement
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
Context
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.
The Strong Reconstruction Conjecture of Bowler, Brown and Fenner is the quantitative frontier of the reconstruction-number literature around the celebrated Kelly-Ulam problem. Disproving it, and showing overlap can approach the full deck, reshapes that frontier - specialist but consequential, at 20.
People
Attempts
No person has examined this. 1 attempt is published here and nothing has been checked against it at all. Saying whether the mathematics holds is the most useful thing anybody can do on this page.
Per the author's public statements (not disclosed in the paper itself): GPT-5.6 Sol proved most of the roughly 400 intermediate theorems explored, with the author supplying the decisive construction idea and direction - in the author's words, the models "could not achieve the goal before I can point to the right idea". Model-proved steps inside a human-led search is recorded as ai-co-developed.
Reviews
No person has reviewed this attempt. It has not been checked at all.
Discussion of this attempt
no comments
Solve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.
Discussion
Nothing has been said about this problem yet.
Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.