The graph reconstruction conjecture, also known as the reconstruction conjecture, Kelly-Ulam conjecture, or Ulam's conjecture, asserts that every simple finite graph on at least three vertices is reconstructible. Equivalently, every such graph is determined, up to graph isomorphism, by its graph deck of one-vertex-deleted vertex-induced subgraphs.
More explicitly, if 
and 
are graphs on 
vertices such that the vertex-deleted subgraphs 
and 
can be paired so that all corresponding cards are isomorphic, then the conjecture asserts that 
and 
are themselves isomorphic.
The graph reconstruction conjecture is due to Kelly and Ulam. Kelly (1957) proved the conjecture for trees and Ulam (1960) popularized the general problem.
McKay (2022) computationally verified the graph reconstruction conjecture and the set reconstruction conjecture for all graphs with at most 13 vertices, as well as for some limited classes of larger graphs.
Tsoukalas et al. (2026) reported an AI-driven formally verified proof of a weak bipartite graph reconstruction theorem. Here "weak" indicates that the theorem concerns a structured bipartite incidence-deletion graph deck and assumes that the graph is biconnected and has pairwise distinct vertex types, where a vertex type consists of the vertex degree together with the multiset of vertex degrees of adjacent vertices. In this variant, the deck determines the graph up to bipartite graph isomorphism. Note that this result is not a proof of the full graph reconstruction conjecture.
