[#P49] Graph reconstruction conjecture
Problem. Every finite simple graph \(G\) with at least three vertices is determined up to isomorphism by the multiset \(\{G-v:v\in V(G)\}\) of its one-vertex-deleted subgraphs.
1Context
Each card in the deck loses a vertex label and all incident edges, so the problem asks whether the overlapping partial views recover the original graph.
2Problem setup
Definition 1 (The deck of a graph). The deck of a graph is the multiset of unlabeled graphs obtained by deleting each vertex once.
Definition 2 (Reconstruction). Reconstruction means that no nonisomorphic graph has the same deck.
Remark 1. Each card in the deck loses a vertex label and all incident edges, so the problem asks whether the overlapping partial views recover the original graph.
3What counts as a solution
- Prove reconstruction for every finite simple graph with at least three vertices, or give two nonisomorphic such graphs and rigorously verify that their decks are identical.
1Status
Current status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: Aravind and Monikandan prove reductions using domination and vertex-pair parameters. Their 2026 paper states the reconstruction conjecture and does not resolve the general case. Exact unresolved remainder: Prove that every finite simple graph with at least three vertices is determined by its vertex-deleted deck, or give two nonisomorphic such graphs with identical decks.[1]
1Packet records
Recent contributions
These records are attached to this problem after the current published packet. Each badge shows its current verification or packet-review step.
Notes and companion material
Original intake status. The cited 2026 paper states the reconstruction conjecture and proves reductions without resolving the general case. The source and public status were checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.
- Many graph classes and all graphs through substantial finite orders are reconstructible. A counterexample must have at least three vertices and match decks as multisets.
Computational notes
- Exhaustive generation verifies bounded vertex counts only.
2See also
- Cycle Double Cover Conjecturegraph theory
- Is there a truly subcubic algorithm for weighted APSP?graph theory
- The Total Coloring Conjecturegraph theory
How to cite
TheoremDB contributors, “Graph reconstruction conjecture,” TheoremDB research memory, snapshot of July 31, 2026. https://theoremdb.org/statements/graph-reconstruction-conjectureThis page as plain text: graph-reconstruction-conjecture.md
This problem includes 2 records joined by 2 typed links, sourced from arxiv.org[1], current as of July 31, 2026.
1References
- Packet source. J. Antony Aravind and S. Monikandan, “A Reduction of the Reconstruction Conjecture using Domination and Vertex Pair Parameters”. arXiv:2601.00620 (2026). J. Antony Aravind and S. Monikandan, arXiv:2601.00620, abstract. ↗preprint · primary source · arXiv:2601.00620, checked 2026-07-31 · checked 2026-07-31Source use: original summary.The cited 2026 paper states the reconstruction conjecture and proves reductions without resolving the general case. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at abstract and reduction theorems.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Supplies current reductions without claiming a general reconstruction theorem.Source named by the research packet.
An original CC0 restatement prepared by TheoremDB maintainers.