Kelly's reconstruction conjecture for graphs

Let GG be a graph on nn vertices. For each vertex vV(G)v\in V(G), let GvG_v be the subgraph obtained by deleting vv from GG, and let

D(G)={GvvV(G)}D(G)=\{G_v\mid v\in V(G)\}

be the multiset of all vertex-deleted subgraphs, called the deck. Kelly's reconstruction conjecture. Any two graphs GG and HH on n>2n>2 vertices with equal multisets D(G)D(G) and D(H)D(H) are isomorphic. This is a classical open problem in graph theory: it asks whether a graph is determined up to isomorphism by its vertex-deleted subgraphs, although important special cases are known.

Sources & referencesView supporting material

Primary source

David Hartman, Aneta Pokorná, Daniel Trlifaj and Lluís Vena, “Reconstructing graphs and their connectivity using graphlets”, arXiv:2508.19189 (2025).

Additional references

3 papers in this index state this conjecture (2014–2025). The statement above is taken from the most recent of them; the others are arXiv:1808.10034, arXiv:1406.7870.

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.