Reconstruction Conjecture

Reconstruction conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph. For $v\in V$, the vertex-deleted graph $G-v$ is the induced graph on $V\setminus\{v\}$: the vertex and all its incident edges are removed. Write $[H]$ for the isomorphism class of an unlabelled graph $H$, where graph isomorphism is a vertex bijection preserving adjacency in both directions.

The vertex deck of $G$ is the multiset \[ \mathcal D(G)=\{\!\{[G-v]:v\in V\}\!\}. \] There is one card for each vertex, and repeated isomorphism classes are retained with their multiplicities. Neither the deleted vertex's identity nor a consistent labelling across the cards is supplied.

The reconstruction conjecture states that for any finite simple graphs $G,H$ with at least three vertices, \[ \mathcal D(G)=\mathcal D(H)\quad\Longrightarrow\quad G\cong H. \] Equality of decks includes equality of multiplicities, hence their cardinalities and the orders of the original graphs. Both connected and disconnected graphs, including isolated vertices, are allowed.

The claim is uniqueness up to isomorphism, not recovery of an original vertex labelling. A counterexample would be a pair of nonisomorphic simple graphs on the same number of at least three vertices with identical decks. Matching a selection of cards, or merely matching counts of small subgraphs, is weaker than deck equality. Directed graphs, parallel edges and loops are outside this formulation, since altering the graph class changes the reconstruction question.

Short English statement

Is every finite simple graph with at least three vertices uniquely determined up to isomorphism by its multiset of vertex-deleted graphs?

Research attempt

Scope and literature check.

Kelly's original paper [A1] contains the subgraph-counting observation behind reconstruction arguments. We prove its elementary counting mechanism and use it to give a complete reconstruction algorithm for regular graphs. This is an established special case, not a new resolution. The source page [S2] and Kelly's paper were checked on 1 October 2026. We then isolate the loss of vertex alignment that prevents this algorithm from extending automatically to graphs with varying degrees.

What an unlabelled deck actually determines.

Let the deck have $n\ge3$ cards $D_1,\ldots,D_n$, with $m_i$ edges in card $i$. Every original edge occurs in exactly $n-2$ cards, so \[ m=|E(G)|=\frac{\sum_i m_i}{n-2}. \] The deleted vertex corresponding to card $i$ had degree $m-m_i$. Consequently the multiset of vertex degrees is reconstructible even though no consistent vertex labels across cards are supplied. More generally, for a fixed graph $F$ with $k<n$ vertices, let $i(F,J)$ count vertex subsets of $J$ inducing a copy of $F$. Every such subset in $G$ survives in exactly $n-k$ cards, hence \[ i(F,G)=\frac{\sum_i i(F,D_i)}{n-k}. \] This identity includes multiplicities and is valid for disconnected $F$ too. It is a counting identity, not a way to identify which occurrences in two cards represent the same original vertices.

A complete regular-graph reconstruction.

Suppose the degree multiset just computed is constant, equal to $r$. Then every graph with this deck is $r$-regular, so regularity is recognized rather than being assumed of a competing realization. Choose any one card $D=G-v$. Its vertices have degrees either $r$ or $r-1$: deleting $v$ lowers precisely its neighbours' degrees by one. Adjoin a new vertex and connect it to every degree-$(r-1)$ vertex of $D$, and to no degree-$r$ vertex. The result is isomorphic to $G$. There is no arbitrary matching step and no hidden choice among same-degree vertices. Any isomorphism between two copies of the card preserves their degrees and therefore extends to the reconstructed graph. For $r=0$ the instruction joins the new vertex to none; for $r=n-1$ it joins to every card vertex. Thus empty and complete graphs are covered as well.

Why a degree-only generalization is insufficient.

For a general graph, a card vertex of degree $d$ could have had original degree $d$ and been a non-neighbour of the missing vertex, or original degree $d+1$ and been a neighbour. The deck determines how many vertices have each original degree but does not assign those degrees to the vertices of this particular card. Choosing such assignments independently across cards is not justified. As a basic stress test, $C_6$ and the disjoint union of two triangles both have six vertices, six edges, and constant degree two; those numerical invariants alone cannot distinguish them. Their actual cards do distinguish them: a card of $C_6$ is a five-vertex path, whereas a card of the other graph is a triangle plus an edge. The regular reconstruction above uses this full card structure, not merely the degree multiset.

Verification and first remaining gap.

A finite enumeration checks the reconstruction procedure on every labelled regular graph with $3\le n\le5$ and every possible deleted vertex. Degrees recovered from deck edge counts agree with the originals, and adding the missing vertex by the deficit rule restores the original labelled adjacency on surviving vertices. The proof handles all orders independently of that check. The factor $n-2$ explains the lower bound on $n$; it is not legitimate to use this formula on two vertices. For nonregular graphs, the unresolved step is a consistent assignment of original degrees and neighbourhoods that is forced by the entire unlabelled deck. No uniqueness theorem for that step is proved here.

Reproducibility.

The finite calculations above are implemented in scripts/check_attempt_batch_2026_10_01.py; run it with Python 3 from the repository. It uses exact integer arithmetic and no external packages.

Final status.

UNRESOLVED. Regular graphs are reconstructed with an explicit, verified procedure and the obstruction to the naive nonregular extension is identified. The universal reconstruction conjecture is not settled. Completion estimate: 5%.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3103 (OPG-658), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Reconstruction conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/reconstruction_conjecture.
• A1 P. J. Kelly, A congruence theorem for trees, Pacific Journal of Mathematics 7 $1957$, 961--968, especially the initial counting lemmas. https://msp.org/pjm/1957/7-1/pjm-v7-n1-p14-p.pdf.

Reconstruction Conjecture

Definitions and mathematical statement

For a finite simple undirected graph $G=(V,E)$, its deck is the multiset of unlabelled isomorphism classes \[ \mathcal D(G)=\left\{\!\left\{[G-v]:v\in V\right\}\!\right\}, \] where $G-v$ is the induced graph obtained by deleting $v$ and all incident edges. The reconstruction conjecture asserts that for graphs $G,H$ on at least three vertices, \[ \mathcal D(G)=\mathcal D(H)\quad\Longrightarrow\quad G\cong H. \] Multiplicity matters: equal-looking vertex-deleted graphs can occur several times in the deck. The vertices removed are not labelled or matched in advance. Edge-deletion reconstruction and reconstruction from only some cards are different questions.

Formulation and concept references: [S1].

Short English statement

Can every graph with at least three vertices be recovered up to isomorphism from the multiset of graphs obtained by deleting one vertex?

Research attempt

Status: UNRESOLVED. The deck is shown to determine the edge count, degree multiset, all proper induced-subgraph counts, connectivity and disconnected components. Complete reconstruction arguments are given for disconnected graphs, regular graphs and graphs with a universal vertex. An exact finite enumeration checks small orders. The unresolved step is compatibility of the unlabelled overlaps in general connected irregular graphs.

Source audit and the two reconstruction models.

The publisher URL [S1] did not yield its full text in this audit. The author's primary preprint [E1] identifies the article as Graph Reconstruction from Connected Triples. That paper's main data consist of specified triples of a vertex set that induce connected graphs; its introduction discusses the classical reconstruction conjecture, but its main theorem is not a proof of reconstruction from the multiset of vertex-deleted unlabelled cards. The distinction is important: the triples come with a common vertex set, whereas the catalogue's cards do not come with compatible vertex labels. We keep the catalogue statement unchanged and prove the following deck consequences directly.

For a graph $F$ let $i(F,G)$ count subsets of $V(G)$ whose induced graph is isomorphic to $F$. This counts vertex subsets, not embeddings or automorphisms. All card statistics below are summed with their multiplicities in the deck.

1. The number of edges and every vertex degree.

The number of cards is $n=|V(G)|$. Each edge survives in exactly $n-2$ cards, so for $n\ge3$, \[ e(G)=\frac1{n-2}\sum_{C\in\mathcal D(G)}e(C). \] For the card obtained by deleting $v$, \[ d_G(v)=e(G)-e(G-v). \] Thus the deck determines the multiset of degrees, even though it does not identify a common labeling of the deleted vertices. In particular it determines the number of isolated vertices, the maximum degree and regularity. At $n=2$ the division fails for a substantive reason: an edge and two isolated vertices have the same two singleton cards. This explains the lower-order exclusion in the conjecture.

2. Proper induced-subgraph counts.

If $F$ has $r<n$ vertices, every induced copy of $F$ in $G$ survives deletion of exactly $n-r$ vertices. Therefore \[ \sum_{C\in\mathcal D(G)}i(F,C)=(n-r)i(F,G), \qquad i(F,G)=\frac1{n-r}\sum_C i(F,C). \] This is the induced form of the familiar counting lemma. It recovers triangles, independent sets of every proper size, and all other proper induced types. The formula has no conclusion at $r=n$: then each whole-graph copy survives in zero cards. Substituting $r=n$ and cancelling a zero factor would assert precisely the missing reconstruction theorem.

Complements give another exact reduction. Since $\overline{G}-v=\overline{G-v}$, complementing every card yields the deck of $\overline G$. Hence any reconstructible class also gives its class of complements. This does not mean that a deck may freely be complemented without changing the problem; it provides a deterministic correspondence between two decks.

3. Connectivity is recognizable.

A connected graph with at least two vertices has a connected vertex-deleted card: choose a spanning tree and delete a leaf of that tree. The remaining tree still spans the remaining vertices. Conversely, suppose $G$ is disconnected and has no isolated vertices. Every component has at least two vertices, so deleting one vertex leaves at least two nonempty components. Every card is disconnected.

It follows, for $n\ge3$, that \[ G\text{ is connected}\quad\Longleftrightarrow\quad G\text{ has no isolated vertices and some card is connected}. \] Both properties on the right are known from the deck, the first from the degree multiset. The explicit isolated-vertex condition is necessary: the graph consisting of one isolated vertex and a connected $(n-1)$-vertex component has a connected card despite being disconnected.

4. Complete reconstruction of disconnected graphs.

Once disconnectedness is recognized, every component has fewer than $n$ vertices. We may therefore use the preceding count formula for each possible connected component type. Work downwards in component order. Suppose all component types of size greater than $r$ and their multiplicities have already been recovered. For each connected graph $F$ on $r$ vertices, subtract from $i(F,G)$ all induced copies lying inside those recovered larger components.

A connected induced copy cannot meet two different components. A component smaller than $r$ contributes nothing. A component of size exactly $r$ contributes one if it is isomorphic to $F$ and zero otherwise. Thus the remaining count is exactly the number of components of type $F$. This determines all component multiplicities, including isolated vertices at the final stage $r=1$, and therefore determines $G$ up to isomorphism.

The procedure is finite: for each $r<n$ there are finitely many graphs to enumerate. It is not presented as a polynomial-time algorithm. Its point is uniqueness from the deck. There is no circular use of reconstruction on individual components; their isomorphism types are explicitly enumerated and their counts are obtained from smaller cards.

5. Complete reconstruction of regular graphs.

Suppose the degree multiset is constantly $d$. Choose any card $C$. Each vertex of $C$ has degree $d$ or $d-1$, according as it was nonadjacent or adjacent to the deleted vertex. Attach a new vertex precisely to the vertices of degree $d-1$. The resulting graph is $G$.

Every graph with the same deck has the same constant degree multiset and is therefore obtained by this same rule from that chosen card. This proves uniqueness. No matching of vertices between different cards is required. The argument also handles $d=0$: the card has only isolated vertices and the added vertex has no neighbors. At the other extreme it recovers complete graphs. Complementation gives no new difficulty because complements of regular graphs are regular.

Similarly, if the deck-derived maximum degree is $n-1$, then a card with exactly $e(G)-(n-1)$ edges deletes a universal vertex. Choose such a card and attach a vertex to all of its vertices. The edge-count criterion identifies the required type of card without labels, proving reconstruction for every graph with a universal vertex. By complementing, this also gives the class with an isolated vertex, though that class is already covered by the disconnected argument.

6. What a candidate-extension search can and cannot prove.

A finite exact search is straightforward. Choose one card $C$ on $n-1$ vertices. For every subset $S\subseteq V(C)$, form $C$ with a new vertex adjacent to $S$, compute its unlabelled deck, and retain it if the deck equals the input deck. The original graph occurs among these candidates. The conjecture asks that all retained candidates be isomorphic.

The degree of the deleted vertex reduces the search to subsets of one known size, but it does not identify the subset. Two vertices of a card with equal degrees need not be interchangeable by an automorphism. Conversely, two choices of $S$ may produce isomorphic extensions even when a particular labeling makes them look different. A correct implementation must compare graph isomorphism classes and preserve repeated card multiplicities.

One tempting induction is to reconstruct every card from its own deck and glue the results. However, the cards already appear as known unlabelled graphs; their further reconstruction adds no labels identifying their overlaps inside $G$. Even knowing the multiset of all two-vertex deletions does not canonically identify which occurrences belong together. The ambiguity is a gluing problem, not a lack of access to smaller induced isomorphism types.

7. A polynomial invariant illustrates the final missing coefficient.

Let $I_G(z)=\sum_{r=0}^n a_rz^r$ count independent vertex subsets. For every $r<n$, $a_r$ is reconstructible by taking $F$ to be the edgeless graph of order $r$ in the count formula. The coefficient $a_n$ is also known because it is one exactly when $e(G)=0$. Thus the independence polynomial is reconstructible.

This observation is useful but does not prove graph reconstruction: different nonisomorphic graphs may share such a polynomial, and an invariant being recoverable is not the same as its being complete. A proposed proof using a larger family of invariants needs an additional argument showing that equality of those invariants forces isomorphism. Invoking all induced counts through order $n-1$ simply restates the information whose sufficiency is at issue.

8. Finite enumeration and the remaining gap.

The offline diagnostic enumerates labelled simple graphs through five vertices and assigns each a canonical code by testing every vertex permutation. It then computes decks as sorted lists of canonical card codes and checks that no deck has two different canonical graph codes at orders three through five. The two-vertex collision is retained as a negative control. It separately verifies the edge and induced-count identities and the reconstruction rules for disconnected, regular and universal-vertex cases in this range.

This is an exhaustive finite check at those orders, not an extrapolation to all graphs. In the general connected irregular case, the deck forces many numerical constraints, but the argument has not shown that exactly one orbit of attachment subsets survives the extension search. Eliminating that ambiguity, by a new invariant or a valid compatibility theorem, is the unresolved part of the catalogue question.

Sources

• S1 Yaxin Qi, Discrete Mathematics 349 $2026$, 115058. https://www.sciencedirect.com/science/article/abs/pii/S0012365X26000828. Formulation source.
• E1 Yaxin Qi, Graph Reconstruction from Connected Triples, primary preprint arXiv:2309.10113. https://arxiv.org/abs/2309.10113. Used to identify the distinct information model of the inherited formulation source.