Open problem, Combinatorics and discrete mathematics, posed 1941

Graph reconstruction conjecture

Open

Let $G$ and $H$ be finite simple undirected graphs on $n \ge 3$ vertices. If their decks—the multisets of unlabeled vertex-deleted induced subgraphs $\{G - v : v \in V(G)\}$ and $\{H - w : w \in V(H)\}$ —are isomorphic card by card, then $G$ is isomorphic to $H$ .

Research frontier as of 2026

As of 2026, the graph reconstruction conjecture remains open for general finite simple graphs. It is known to hold for all graphs with $n \le 13$ vertices (McKay, 2022), for trees, disconnected graphs, regular graphs, unicyclic graphs, cacti, outerplanar graphs, and maximal planar graphs, as well as asymptotically for almost all graphs. Graph invariants known to be reconstructible from the deck include the degree sequence, connectedness, the number of spanning trees, the characteristic polynomial, and the chromatic and Tutte polynomials, yet general planar graphs and bipartite graphs remain unsettled.

Best known results

Every graph on $3 \le n \le 13$ vertices is uniquely reconstructible—even from the set of isomorphism types in its deck (McKay, 2022).
Trees, disconnected graphs, regular graphs, outerplanar graphs, and maximal planar graphs are reconstructible; moreover, planarity itself is recognizable from the deck.
With probability tending to $1$ as $n \to \infty$ , a random graph $G(n, 1/2)$ is uniquely determined by any $3$ of its vertex-deleted subgraphs (Bollobás, 1990).

Tools and where they stop

Tool	Achieved	Where it stops
Kelly's counting lemma and subgraph algebra	Determines the exact number of occurrences of any subgraph $F$ with $\|V(F)\| < n$ because each copy of $F$ appears in exactly $n - \|V(F)\|$ cards of the deck, recovering degrees, trees, disconnected graphs, and the Tutte polynomial.	Cannot directly count spanning subgraphs ( $\|V(F)\| = n$ ) such as Hamiltonian cycles, nor tell how the pieces on different cards fit together in highly symmetric 2-connected graphs.
Inclusion-exclusion and Lovász–Müller edge-counting method	Proves the edge reconstruction conjecture for all graphs with $m > n \log_2 n$ edges by comparing automorphism group sizes via inclusion-exclusion over edge subsets.	The alternating sum in inclusion-exclusion requires $2^m > n!$ , failing in the sparse regime $m \le n \log_2 n$ where most hard vertex-reconstruction cases also live.

Open questions

Is every finite planar graph or every finite bipartite graph on $n \ge 3$ vertices reconstructible from its vertex-deleted deck?
Does Harary's edge reconstruction conjecture hold for all sparse graphs with $4 \le m \le n \log_2 n$ edges?

References

Paul J. Kelly (1957). A congruence theorem for trees · DOI:10.2140/pjm.1957.7.961
J. A. Bondy, R. L. Hemminger (1977). Graph reconstruction—a survey · DOI:10.1002/jgt.3190010306
Brendan D. McKay (2022). Reconstruction of small graphs and digraphs