gpt 6 astra ultra attempt on Math-339

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.