The Reconstruction conjecture is a hypothesis in graph theory that asserts:
Every finite simple graph with at least three vertices is uniquely determined (up to isomorphism) by the multiset of its vertex‑deleted subgraphs, commonly called its deck.
Formal statement
Let $G$ be a finite simple graph with $|V(G)| \ge 3$. For each vertex $v \in V(G)$, define the card $G - v$ as the subgraph obtained by deleting $v$ and all edges incident to it. The deck of $G$ is the multiset ${,G - v : v \in V(G),}$. The conjecture claims that if two graphs $G$ and $H$ have identical decks, then $G$ and $H$ are isomorphic.
Historical background
- The problem originates from a question posed by Stanislaw Ulam in the 1940s concerning the reconstruction of structures from partial information.
- Kelly formalized the graph‑theoretic version in 1957, publishing the conjecture in Pacific Journal of Mathematics.
Known results and partial confirmations
| Class of graphs | Status |
|---|---|
| Trees | Proven (Kelly, 1957) |
| Regular graphs of degree ≥ 2 | Proven (Harary, 1960s) |
| Disconnected graphs with at most one non‑trivial component | Proven |
| Graphs with ≤ 11 vertices | Verified by exhaustive computer search |
| Locally finite graphs, certain families of chemical graphs | Partial results |
| All graphs up to 29 edges (computational) | Verified |
Various reduction theorems show that proving the conjecture for all graphs would follow from proving it for certain restricted families (e.g., 2‑connected graphs). No counterexample is known; the conjecture remains open.
Related concepts
- Edge‑reconstruction conjecture: analogous statement using edge‑deleted subgraphs. Proven for many graph classes but also open in general.
- Reconstruction numbers: minimum size of a subdeck needed to guarantee reconstruction; known for some graph families.
- Kelly’s lemma: provides counts of subgraphs that can be derived from the deck, forming a basis for many partial results.
Current status
As of the latest literature (up to 2023), the Reconstruction conjecture remains unsolved. It is listed as a notable open problem in standard references such as the Open Problems in Mathematics and the Kleitman–Mader survey. Ongoing research focuses on improving reconstruction algorithms, establishing the conjecture for broader families, and exploring connections with graph invariants and combinatorial reconstruction theory.
