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
- Result
- Disproved(see note)
- Status
- Resolved
- AI contribution
- AI co-developed
- Method
- Construction
- Field
- Graph theory - reconstruction
- Posed by
- Andrew Bowler, Paul Brown, Trevor Fenner
- Year posed
- 2010
- Years open
- 16y
- Solved
- 2026-08-12
- Model
- gpt-5.6-sol
- Vendor
- —
- Collaborators
- —
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 20 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
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.
What the AI did
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.
Verification
Checked by this site on 17 August 2026 against the paper's LaTeX (arXiv:2608.11930, Ivanov) and its verification repository, which the paper's own footnote links. Two submitted claims needed correcting. The entry arrived Expert-verified on the strength of the author's own LinkedIn post - self-endorsement is not independent expert verification, so this is Unreviewed. And the paper itself contains NO AI disclosure: the account of GPT-5.6 Sol's role rests entirely on the author's public statements outside the paper, which this entry now says explicitly. The nauty deck checks are author-side. The construction was not verified here.
Source
- Paperarxiv.org
Submitted by FrostyVulture999 on