The reconstruction conjecture for finite simple graphs

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

D(G)={ ⁣{Gv:vV(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.

Sources & referencesView supporting material

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.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.