Math Conjectures

Graph Reconstruction Conjecture

OPENLandmarkConjectureProposed 1942 · Standard version

Canonical statement

If GG and HH are finite simple graphs on the same number n≥3n\geq3 of vertices and the multisets of unlabeled graphs
{ G−v:v∈V(G) }and{ H−w:w∈V(H) } \{\,G-v:v\in V(G)\,\} \quad\text{and}\quad \{\,H-w:w\in V(H)\,\}
are equal, then G≅HG\cong H, where G−vG-v denotes the induced graph obtained by deleting vv.
View source LaTeX
If \(G\) and \(H\) are finite simple graphs on the same
number \(n\geq3\) of vertices and the multisets of unlabeled graphs
\[
  \{\,G-v:v\in V(G)\,\}
  \quad\text{and}\quad
  \{\,H-w:w\in V(H)\,\}
\]
are equal, then \(G\cong H\), where \(G-v\) denotes the induced graph
obtained by deleting \(v\).
GRAPH-002:[Bondy1991Reconstruction][DufresneEtAl2026Reconstruction]
Graph theoryTheoretical computer science

Notes

The deck of a finite simple graph GG is the multiset of unlabeled vertex-deleted subgraphs G−vG-v. The reconstruction conjecture, dating from 1942 and traditionally associated with Kelly and Ulam, asserts that any two graphs on n≥3n\ge3 vertices with the same deck are isomorphic; the hypothesis n≥3n\ge3 is needed because the two graphs on two vertices have identical decks. Bondy's manual remains the standard account of the problem [Bondy1991Reconstruction].

Much is known short of a full proof. Many invariants, including the number of edges, the degree sequence, and connectedness, are determined by the deck, and broad classes such as trees, regular graphs, and disconnected graphs are reconstructible; exhaustive computation has also verified the conjecture over substantial finite ranges of nn [Bondy1991Reconstruction]. A recent line of work recasts the problem in the language of invariant theory [DufresneEtAl2026Reconstruction]. The edge-reconstruction conjecture, in which edges rather than vertices are deleted, is a distinct problem rather than an equivalent formulation.

No argument is known that covers all finite simple graphs, and the conjecture remains open.

References (2)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.