Reconstruction Conjecture: is every graph on ≥3 vertices determined by its deck of vertex-deleted subgraphs?
Statement
The *deck* of a graph $G$ on $n$ vertices is the multiset of its $n$ vertex-deleted subgraphs $G - v$ (each given up to isomorphism). $G$ is *reconstructible* if it is the only graph (up to isomorphism) with that deck. The Reconstruction Conjecture (Kelly 1957, Ulam) asserts that **every graph on at least $3$ vertices is reconstructible from its deck**. Decide the conjecture, or find two non-isomorphic graphs on $\ge 3$ vertices with the same deck. Computational sub-question: verify that all graphs on $n$ vertices are reconstructible, extending the current exhaustive bound.
Acceptance. FULLY RESOLVES: (a) two non-isomorphic graphs on $\ge 3$ vertices with identical decks (a certificate matching the two multisets of vertex-deleted subgraphs up to isomorphism), refuting the conjecture; or (b) a proof. PARTIAL PROGRESS: an exhaustive verification, via $\texttt{nauty}$ deck computation and canonical-form matching, that all graphs on $n = 14$ vertices (or a nontrivial new class) are reconstructible, extending McKay's $n \le 13$ result. Provide the deck-canonicalization pipeline and the count checked.
Background
Frontier: McKay (2022) computationally verified the reconstruction conjecture (and the set-reconstruction conjecture) for all graphs with at most $13$ vertices (arXiv:2102.01942, 'Reconstruction of small graphs and digraphs'); the number of graphs on $13$ vertices is $50{,}502{,}031{,}367{,}952$. The edge-version and many classes (regular graphs, trees, disconnected graphs, etc.) are proved. Digraphs are known to be *not* reconstructible in general. Still open for graphs. Source: Open Problem Garden, 'Reconstruction conjecture' (www.openproblemgarden.org/op/reconstruction_conjecture), originators P. J. Kelly and S. M. Ulam; see also MathWorld, 'Graph Reconstruction Conjecture'.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Reconstruction conjecture — Open Problem Garden | link |
| REF-02 | McKay, Reconstruction of small graphs and digraphs (verified ≤13 vertices, 2022) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.