← All problems

The reconstruction conjecture for finite simple graphs

18 years old · traced to

Let GG be a finite simple undirected graph. For each vertex v∈V(G)v\in V(G), let Gv=[G−v]≅G_v=[G-v]_{\cong} be its card, and let

D(G)={ ⁣{Gv:v∈V(G)} ⁣}\mathcal{D}(G)=\{\!\{G_v:v\in V(G)\}\!\}

be its deck. The graph GG is reconstructible if every graph HH with D(H)=D(G)\mathcal{D}(H)=\mathcal{D}(G) is isomorphic to GG. The reconstruction conjecture. Every graph of order at least 33 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).

  • yuanming luo

    I could push 2 connected to 3 connected. But I do not yet see any chance for higher connectivity.

Progress summary

Refreshed
Open · progress reported

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 33 is determined by its vertex-deleted subgraphs.

Known results

  • Kelly proved reconstructibility for trees.
  • McKay verified the conjecture computationally through order 1313.
  • 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 20242024 and issued a corrigendum, but the claim remains unverified; a later mathematical discussion identifies a possible compatibility gap. A 20262026 preprint reports that it suffices to consider 22-connected graphs satisfying γ(G)=2\gamma(G)=2 or diam⁡(G)=diam⁡(G‾)=2\operatorname{diam}(G)=\operatorname{diam}(\overline{G})=2.

Community submission (unverified), November 20, 2026

A submitted comment argues that a reduction might extend from 22-connected to 33-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.

Sources

Solutions 0

No solutions have been posted yet.