MathDB

The reconstruction conjecture for finite simple graphs

About 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

Primary source

Irene Heinrich, Masashi Kiyomi, Yota Otachi and Pascal Schweitzer, “Interval Graphs are Reconstructible”, arXiv:2504.02353 (2026).

Additional 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.

graph-reconstructioninterval-graphsstructural-graph-theory
Posted · edited

Progress summary

Refreshed
Claimed solved

The conjecture remains officially open: a claimed general proof appeared in 2024, but it has not been accepted, while several important special cases are known.

The conjecture, attributed to Ulam and Kelly, says that every finite simple graph with three or more vertices is determined by its vertex-deleted subgraphs. It remains a central open problem despite extensive computational and structural results.

Known results

  • McKay verified the conjecture computationally for graphs with at most 1313 vertices.
  • Kelly proved reconstructibility for trees.
  • Many classes are known, including regular, disconnected, outerplanar, unicyclic, threshold, and unit interval graphs.
  • Bollobás proved that almost all graphs are reconstructible from three suitably chosen cards.

Claimed general proof and recent special case, 2024–2026

Robert J. O’Shea and Louis Wilkins published a 20242024 article claiming a proof for all finite undirected graphs; a corrigendum followed, but the claim remains unverified. A later discussion identifies a possible compatibility gap between card isomorphisms. Heinrich, Kiyomi, Otachi, and Schweitzer’s preprint, revised in May 20262026, proves reconstructibility and gives a polynomial-time algorithm for interval graphs.

Current status (as of September 2026): The full conjecture has no accepted proof or counterexample; O’Shea–Wilkins’ claimed proof is unverified, while the interval-graph case and many other restricted classes are settled.

Sources

Solutions 0

No solutions have been posted yet.