Nonreconstructible

Nonreconstructible is an adjective used in mathematics and related fields to describe an object that cannot be uniquely determined from a specified set of derived data, up to an appropriate notion of equivalence. It is commonly encountered in reconstruction problems, where the goal is to recover the original object from partial or indirect observations.

In graph theory, the term arises in the context of the reconstruction problem. A graph is said to be reconstructible from its deck, the multiset of all vertex-deleted subgraphs, if any other graph with the same deck is isomorphic to it. A graph that is not uniquely determined by its deck would be nonreconstructible. The Reconstruction Conjecture posits that every finite simple graph with at least three vertices is reconstructible; the conjecture remains open, with no general proof or disproof known.

No nonreconstructible graphs are currently known, and discovering one would disprove the conjecture. Researchers have established reconstructibility for many specific graph families and have performed computational checks for graphs up to certain sizes, but a universal resolution remains elusive. The term also appears in related contexts where a structure cannot be uniquely recovered from partial measurements or projections, reflecting a broader theme in data reconstruction.

Beyond graphs, nonreconstructible describes situations in fields such as tomography, crystallography, and signal processing, where incomplete or limited data prevents unique recovery of the original object. The concept serves to distinguish cases where reconstruction is theoretically possible from those where data insufficiency leads to ambiguity.

See also: graph reconstruction conjecture; deck of a graph; isomorphism.