gpt 6 astra ultra attempt on Math-1043

Edge Reconstruction Conjecture

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple undirected graph with $m=|E|$. For an edge $e\in E$, define $G-e=(V,E\setminus\{e\})$. Only that edge is deleted: every vertex is retained, including endpoints that become isolated and vertices already isolated. The edge deck is the multiset of unlabelled isomorphism classes \[ \mathcal D_E(G)=\{\!\{[G-e]:e\in E\}\!\}. \] Each original edge contributes one card, even if several deletions produce isomorphic graphs. The cards carry no common vertex labels and do not identify which edge was removed.

The conjecture asserts that whenever finite simple graphs $G,H$ each have at least four edges, \[ \mathcal D_E(G)=\mathcal D_E(H)\quad\Longrightarrow\quad G\cong H. \] Here an isomorphism is a bijection of vertex sets preserving adjacency. The hypothesis gives exactly the whole multiset of cards, not only the set of distinct isomorphism types. Its size records the original number of edges, and the vertex count of every card records the original order.

There is no connectedness assumption, and isolated vertices remain part of the object to reconstruct. The lower threshold refers to four edges, not four vertices. The question concerns reconstruction from edge deletion; removing an endpoint as well would produce a different deck. An affirmative answer needs only uniqueness up to isomorphism, whereas a negative answer requires two genuinely nonisomorphic graphs satisfying the complete multiset equality.

Short English statement

Is every finite simple graph with at least four edges determined up to isomorphism by all its edge-deleted cards, counted with multiplicity?

Research attempt

Scope and process.

GPT-6 Astra Ultra, 1 October 2026. This attempt keeps the catalogue statement above, checks primary literature, and develops a restricted argument with an adversarial gap audit. The proofs below are the mathematical output of this attempt, not a claim of novelty or external certification.

Literature and attack plan.

The checked original Garden entry [S2] states the four-edge threshold and cites Bondy's reconstruction manual. We do not infer a general reconstruction theorem from that entry. The route pursued here is to recover a degree invariant by double counting, identify regular graphs from their decks, and recover the missing edge on that recognizable subclass. This also tests whether unlabelled cards really suffice.

Deck double counting.

For a fixed finite graph $F$ with $r<m$ edges, let $N_F(G)$ count copies as subgraphs, not necessarily induced; a copy includes its chosen vertices and edges. Every copy survives exactly the deletions of the $m-r$ edges outside it. Therefore \[ \sum_{C\in\mathcal D_E(G)}N_F(C)=(m-r)N_F(G). \tag{1} \] The sum uses multiplicities. In particular, put $F=P_3$, the two-edge path, and write $W(G)=N_{P_3}(G)$. Choosing its centre and two incident edges shows \[ W(G)=\sum_{v\in V}\binom{d(v)}2, \qquad W(G)=\frac1{m-2}\sum_{C\in\mathcal D_E(G)}W(C). \tag{2} \] A triangle contributes three such copies, because inducedness is not required. This is exactly the convention needed for the degree identity.

Recognizing regularity from unlabelled cards.

The deck determines $m$ by its cardinality and $n$ from the order of any card. Equation $2$ determines \[ Q=\sum_vd(v)^2=2W(G)+2m. \] Consequently the nonnegative quantity \[ Q-\frac{4m^2}{n}=\sum_v\left(d(v)-\frac{2m}{n}\right)^2 \tag{3} \] is reconstructible. It vanishes precisely when every vertex has the common degree $d=2m/n$. Thus if a regular graph and any other graph have the same edge deck, the latter is regular with the same degree as well. This step prevents a hidden assumption that a potential rival is already known to be regular.

Unique completion of a regular card.

Suppose $3$ vanishes. Since $m\ge4$, $d\ge1$. In any card $C=G-uv$, exactly two vertices have degree $d-1$, namely $u,v$; all other vertices have degree $d$. The two exceptional vertices are nonadjacent in $C$. Add their edge. This is the only edge addition making all degrees equal to $d$, and gives a graph isomorphic to $G$.

The reconstruction rule is invariant under graph isomorphism: every isomorphism between two representations of $C$ maps its two deficient vertices to the two deficient vertices. It therefore gives the same isomorphism class without a common labelling of the deck. Any graph $H$ sharing the deck is regular by $3$; applying this rule to a common card yields both $G$ and $H$, so $G\cong H$. This proves the target on all regular graphs, connected or disconnected.

Verification and failure of the unrestricted shortcut.

The reproducible standard-library check in scripts/check_attempt_batch_graphs_2026_10_01.py verifies the wedge-count identity and the applicable regular inverse rules across all 1,024 labelled graphs on five vertices. This finite audit supplements the preceding proofs; it does not certify reconstruction for all graph orders.

For a matching of at least four edges, $d=1$ and the card has precisely two isolated vertices; joining them works. For $C_4$, deleting an edge produces degrees $1,1,2,2$, and the same rule restores the cycle. The argument allows disconnected regular graphs. A regular graph with an isolated vertex would have $d=0$, excluded here by $m\ge4$; we have not silently discarded isolates from arbitrary graphs.

For an irregular graph the two affected vertices need not be identifiable by a common deficit. For example, in the path on five vertices, deleting an end edge produces an isolated vertex and a four-vertex path, whose two endpoints are indistinguishable within the path. This example is not a counterexample to reconstruction; it demonstrates why a vertex-degree rule alone is not a general reconstruction certificate. Equation $1$ also cannot recover $N_G(G)$: its denominator would be zero when $r=m$.

First remaining gap and final status.

The deck invariants and the regular reconstruction theorem are proved. No procedure here selects the missing endpoints in every irregular card or excludes all irregular pairs with the same deck. The original conjecture is UNRESOLVED by this attempt; no positive percentage of a general proof is asserted.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3104 (OPG-804), OpenGarden collection. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Edge Reconstruction Conjecture. Original problem and discussion; the mathematical formulation below is expanded from the supplied source record. http://www.openproblemgarden.org/op/edge_reconstruction_conjecture.