The reconstruction conjecture for finite simple graphs
Let be a finite simple undirected graph. For each vertex , let be its card, and let
be its deck. The graph is reconstructible if every graph with is isomorphic to . The reconstruction conjecture. Every graph of order at least is reconstructible. This is one of the central open problems in structural graph theory, asserting that a graph is determined up to isomorphism by the multiset of its vertex-deleted induced subgraphs. The conjecture remains wide open, although the paper proves it for interval graphs with at least three vertices.
References
9 papers in this index state this conjecture (2008–2025). The statement above is taken from the most recent of them; the others are arXiv:2503.20167, arXiv:2311.16665, arXiv:2210.00338, arXiv:1606.02926, arXiv:1602.02731, arXiv:1004.2375, arXiv:0810.3189, arXiv:0804.4093.
Source: Irene Heinrich, Masashi Kiyomi, Yota Otachi and Pascal Schweitzer, “Interval Graphs are Reconstructible”, arXiv:2504.02353 (2026).
Progress summary
The problem remains open: a claimed proof has not been accepted, while newer work narrows some cases that still need to be understood.
The conjecture, attributed to Ulam and Kelly, says that every finite simple graph of order at least is determined by its vertex-deleted subgraphs.
Known results
- Kelly proved reconstructibility for trees.
- McKay verified the conjecture computationally through order .
- Reconstructibility is known for several classes, including regular, disconnected, outerplanar, unicyclic, threshold, and unit interval graphs.
- Bollobás proved that almost all graphs are reconstructible from three suitably chosen cards.
2024 claimed proof and 2026 reductions
O’Shea and Wilkins claimed a general proof in and issued a corrigendum, but the claim remains unverified; a later mathematical discussion identifies a possible compatibility gap. A preprint reports that it suffices to consider -connected graphs satisfying or .
Community submission (unverified), November 20, 2026
A submitted comment argues that a reduction might extend from -connected to -connected graphs, but says it has no route for higher connectivity.
Current status (as of November 2026): The full conjecture remains open with no accepted proof or counterexample; the O’Shea–Wilkins proof claim is unverified, the 2026 reduction is a reported partial advance, and the community submission is unverified.
Solutions 0
No solutions have been posted yet.
I could push 2 connected to 3 connected. But I do not yet see any chance for higher connectivity.