The Reconstruction Conjecture
A graph on at least three vertices is determined, up to isomorphism, by the multiset of its vertex-deleted subgraphs. You can rebuild the whole from the deck of its one-vertex-smaller pieces.
Formal statement
Obstruction
Why the direct approaches fail
Kelly’s Lemma reconstructs the count of every proper subgraph, and the conjecture is verified for trees, disconnected graphs, regular graphs, and by computer for all graphs on at most eleven vertices. None of that reaches isomorphism. The decisive obstruction is that the directed analogue is false — Stockmeyer built infinite families of non-reconstructible tournaments — so no counting argument that ignores the undirected structure can ever work.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Identify the exact place Stockmeyer’s digraph counterexamples break Kelly-style counting, and whether the failure is repairable for undirected graphs.
- 02Reconstruct a graph’s characteristic polynomial or spectrum from its deck and test whether that determines it.
- 03Attack the equivalent edge-reconstruction question for graphs with more than n·log₂n edges (Müller’s bound).
- 04Determine whether 2-connectivity or a degree condition makes the counting argument sufficient.
Reconstruction has its own lane in the solver, running continuously alongside every other problem.