Graph theory · reconstruction · spectral graph theory

Graph Reconstruction Conjecture

Collaboration beta

Can a finite simple graph on at least three vertices always be recovered, up to isomorphism, from the multiset of all graphs obtained by deleting one vertex?

G, G' finite simple graphs on n \geq 3 vertices, D (G) = D (G') \Rightarrow G ≅ G'

Open Problem Garden — Outstanding four-star problem

Known results and sources

Each card contains almost the whole graph, but the missing-vertex correspondence is hidden: does the complete multiset of cards determine the original graph?

Research problem

Exact mathematical statement

Let $G$ and $G'$ be finite simple graphs on $n\ge 3$ vertices. Their vertex decks are the multisets

D(G)=\{G-v:v\in V(G)\}_{\mathrm{multi}},\qquad D(G')=\{G'-v:v\in V(G')\}_{\mathrm{multi}},

where deleting a vertex also deletes every incident edge and repeated isomorphism types retain their multiplicity. The Graph Reconstruction Conjecture asks whether

D(G)=D(G')\quad\Longrightarrow\quad G\cong G'.

The full conjecture remains open. The retained source develops substantial spectral and combinatorial reductions, candidate low-corank arguments, corrected failed routes, and reported exact computations; none is represented as an accepted proof of the general statement.

Problem infographic

Problem at a glance

Problem-first scientific explainer for the Graph Reconstruction Conjecture, showing a seven-vertex graph, representative one-vertex-deleted cards grouped as a multiplicity-preserving deck, two candidate graphs with equal decks, known reconstructible classes, finite verification through thirteen vertices, and the general case marked open. — The conjecture asks whether equal vertex-deleted decks force two finite simple graphs with at least three vertices to be isomorphic; broad classes and all graphs through thirteen vertices are known, while the general case remains open.

Current mathematical picture

Where work on Graph Reconstruction Conjecture stands

Recent proof claim under review

The retained source develops the graph-reconstruction problem from deck-visible degree and spectral data through a regular-orthogonal reduction and a quadratic-frame obstruction. It records established reconstructible regimes, a source-internal proof for walk rank at least n-1, audit-sensitive proposed conclusions at low walk corank and rank-two ambiguity, exact computations supplied but not rerun here, corrected failed routes, and focused audit and finite-core obligations. The full conjecture remains open.

Leading routeDeck-to-quadratic-frame route

Pass from the graph deck to the generalized characteristic polynomial, regular orthogonal equivalence, non-main-space motion, and the quadratic-frame obstruction.

Route status · Active route

Useful failureWalk-corank-two checkerboard route

Use checkerboard normal form, deletion cyclicity, exceptional migrations, common target triples, cross-side orientation rigidity, and a proposed invariant-direction contradiction.

Route status · Narrowed route

Main reductionDeck-visible reductions organized

The current work assembles degree, card, complement, generalized-polynomial, walk-rank, and apex-moment information into a common reconstruction framework.

Evidence posture · Reported reduction

Completed special caseHigh-walk-rank regime closed internally

The quadratic-frame argument gives a source-internal reconstruction proof whenever the walk matrix has rank at least n-1.

Evidence posture · Reported special case

Priority open bridgeProve the stratified bad-card finite-core lemma

In the decoupled or one-sided coupled corank-three forms, show that the complete family of allowed switched-side card isomorphisms forces either graph isomorphism or non-main dimension at least four.

Task status · Blocked by the current route

Research-record correctionResearch-record correction

We corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Reader-facing record corrected; mathematics unchanged

Work mapped so far

Graph Reconstruction Conjecture in numbers

1.4kretained lines of mathematical investigation1,415 in the current working snapshot

Argument development: 1,216 · 86%
Explored or eliminated routes: 58 · 4%
Computational analysis: 31 · 2%
Open obligations: 17 · 1%
Definitions and setup: 93 · 7%

10selected mapped statements4routes investigated3reported milestones4open questions2contribution-ready tasks

How this is measured

This measures retained mathematical investigation, not proximity to a proof. Code, data, logs, repeated text, operational instructions, and generated presentation copy are excluded.

Proposed byPaul J. Kelly, Stanisław M. UlamProposed1941Status checkedAug 6, 2026

Source recordedAug 5, 2026

Recommended next task

Prove the stratified bad-card finite-core lemma

In the decoupled or one-sided coupled corank-three forms, show that the complete family of allowed switched-side card isomorphisms forces either graph isomorphism or non-main dimension at least four.

Suggested move: After the low-corank audits, stratify by one doubled eigenvalue, one tripled eigenvalue, rank-two-side versions, and only then the two-doubled-eigenspace worst cases.

What would count as progress

All permitted long-cycle multisets and arbitrary involutive collars are handled.
At least one deletion from each switched side is compared.
The proof yields either a global sign-reversing isomorphism or two independent invariant sign modules.

Argument map and routes

How the current approaches connect

Claims, reductions, open questions, active routes, and narrowed alternatives in one mathematical map.

Visible working map

Research route map

20 selected steps

Selected claims, active routes, useful failures, and open questions from the current research map. Arrows appear only for explicitly recorded relationships.

Scroll horizontally to explore the route

Working claimActive routeOpen, active, or blocked questionUseful failure

Working overview, not proof. The map shows selected recorded relationships; more nodes or edges do not establish correctness or completion.

Active routeDeck-to-quadratic-frame route

Pass from the graph deck to the generalized characteristic polynomial, regular orthogonal equivalence, non-main-space motion, and the quadratic-frame obstruction.

Route status · Active route

Active routeWalk-corank-three finite-core route

Audit the rank-two checkerboard classification, then stratify repeated-spectrum card permutations by multiplicity profile and reflection rank to close decoupled and one-sided coupled branches.

Route status · Active route

Explored alternatives

Other routes

2 recorded

Narrowed routeWalk-corank-two checkerboard route

Use checkerboard normal form, deletion cyclicity, exceptional migrations, common target triples, cross-side orientation rigidity, and a proposed invariant-direction contradiction.

Route status · Narrowed route

Route held in reserveHigher-corank ambiguity route

For rank-two ambiguity, audit and exploit the cyclic spectator modules and card reflections; for ambiguity rank at least three, study intersections of moment quadrics and compatible rank-two summands.

Route status · Route held in reserve

Route statements and reductions

Statements the next route can inspect and build on

Route statementDeck mates reduce to non-main orthogonal motion

After matching card occurrences, any hypothetical deck mate is related by a regular orthogonal similarity whose nonpermutation motion is confined to the non-main Krylov complement.

Source-reported route statement

Route statementWalk rank at least n-1 implies reconstructibility

A graph G is reconstructible whenever rank(W_G) >= n - 1.

Source-reported route statement

Route statementProposed walk-corank-three checkerboard classification

The current work proposes that invertible ambiguity is impossible at walk corank three and that any surviving ambiguity has rank two, giving a balanced checkerboard with a decoupled or one-sided spectator coupling.

Source-reported route statement · dependencies incomplete

Route statementProposed repeated-spectrum finite-core bounds

The current work derives multiplicity-excess and reflection-rank bounds that constrain the non-involutory support of switched-side card permutations in terms of walk corank rather than graph order.

Source-reported route statement

More ways to contribute

Open questions

Additional prepared tasks for exploring this research frontier.

4 featured tasks

Audit the all-corank rank-two cyclic splitting

Check the rank-two normal form, checkerboard forcing, Schur-complement identity, cyclic-module orthogonality, resolvent difference, rational-function factor step, coordinate-fixing involutions, and reflection ranks.

Suggested move: Check the signs and block inverses in equations (18.37) and (18.41) before auditing downstream card reflections.

Ready to work on

Audit the corrected walk-corank-two closure

Independently verify the common-target proof, cross-side translation, residual boundary transformations, orthogonality step, incidence decompositions, invariant subspace, and final contradiction.

Suggested move: Begin with the common-target proof and cross-side translation, then use the finite tables only for the explicitly certified orientation and boundary-state substeps.

Ready to work on

Prove the stratified bad-card finite-core lemma

In the decoupled or one-sided coupled corank-three forms, show that the complete family of allowed switched-side card isomorphisms forces either graph isomorphism or non-main dimension at least four.

Suggested move: After the low-corank audits, stratify by one doubled eigenvalue, one tripled eigenvalue, rank-two-side versions, and only then the two-doubled-eigenspace worst cases.

Blocked by the current route

Control ambiguity operators of rank at least three

For non-main dimension at least four, analyze intersections of moment quadrics and decompose or exclude ambiguity operators of rank at least three.

Suggested move: Only after auditing the rank-two branch, study several moment quadrics, finite-direction obstructions, and possible rank-two summand splittings.

Blocked by the current route

Sourced mathematical context

The known mathematical landscape

Context collected Aug 6, 2026

Current statusRecent proof claim under review

The full conjecture remains open: no accepted proof or counterexample is reflected in current 2026 specialist and authoritative sources. O'Shea and Wilkins published a 2024 article claiming a proof for all finite undirected graphs, but later sources continue to state the problem as open, so the claim is recorded without promotion. McKay verified every graph through 13 vertices by exhaustive computation; many infinite families and almost all graphs are reconstructible; and a 2026 Lean development proves only a materially restricted bipartite incidence-deletion variant.

[9][10][14]

External progress

What the literature has established

Selected external milestones in reverse chronological order, with their evidence posture.

2026
PreprintA Google DeepMind project released a Lean proof of a weak bipartite incidence-deletion reconstruction theorem under 2-connectivity and pairwise-distinct vertex-type hypotheses. It is a formally checked…[11][12]
2026
Peer reviewedAsilis, Chen, Hansen, and Teng established robust asymmetry and subgraph-uniqueness results in semi-random models and improved bounds on nonreconstructible probability mass, without settling worst-case…[9]
2026
PreprintDufresne, Jeronimo, Kenkel, Lindo, and Villamizar surveyed the still-open conjecture and developed an invariant-theoretic approach to separating graphs through deck invariants.[10]
2025-2026
PreprintHeinrich, Kiyomi, Otachi, and Schweitzer proved that all interval graphs with at least three vertices are reconstructible and can be reconstructed in polynomial time; the preprint was revised in May 2026.[8]

Mathematical neighborhood

Related results and reusable starting points

Current focusGraph Reconstruction Conjecture

Stronger or generalized formSet Reconstruction Conjecture

Harary's set-reconstruction version discards card multiplicities and asks whether the resulting set still determines a graph. Proving it would imply ordinary deck reconstruction; McKay verified both through 13 vertices.

[6]

Related problemEdge Reconstruction Conjecture

The edge-reconstruction conjecture asks for recovery from the multiset of one-edge-deleted graphs. It is a companion problem with different thresholds and no complement duality.

[1]

Solved special caseclassical reconstructible graph families

Trees, disconnected graphs, and regular graphs are classical reconstructible families. Their solutions provide basic counting and structural techniques but do not cover arbitrary connected irregular graphs.

[2][1]

Solved special caseinterval graphs

Every interval graph on at least three vertices is reconstructible, with a polynomial-time algorithm based on a structure theory resilient to graph separations.

[8]

Weaker or relaxed formaverage-case and semi-random graph reconstruction

Almost-everywhere and semi-random results show reconstruction for overwhelmingly large probabilistic families and under robust perturbations. They do not rule out exceptional worst-case counterexamples.

[4][9]

Dependency or reductionreconstruction of 2-connected graphs

It is enough to settle the conjecture for 2-connected graphs; disconnected and separable structure can be reduced using established reconstruction arguments.

[1]

Equivalent formulationKocay covering-matrix formulation

At a fixed order n, reconstruction is equivalent to equality between the number of graph isomorphism types and the number of decks, and can be represented by full-rank Kocay covering matrices.

[5]

Related problemweak bipartite incidence-deletion reconstruction

The formally proved weak bipartite theorem uses a part-preserving incidence-deletion deck and assumes 2-connectivity plus pairwise-distinct vertex types. Those changes make it a related restricted theorem rather than a case of the exact full statement.

[11][12]

Formal and computational footholds

Existing statements, libraries, computations, and datasets that can shorten the next serious attempt.

formal proof · source linked; not reproduced by ProofAtlasLean proof of weak bipartite graph reconstruction
A public Lean file proves a 2-connected bipartite incidence-deletion variant when all vertex types are pairwise distinct. The formal statement changes the deck, preserves a fixed bipartition, and imposes strong hypotheses; it is not a formal proof or formal statement of the full conjecture.
[11][12]
formal library support · source linked; not reproduced by ProofAtlasMathlib finite simple-graph infrastructure
Mathlib provides simple graphs, induced subgraphs, adjacency, isomorphisms, finite vertex sets, and related combinatorial infrastructure. A deck-as-multiset-of-isomorphism-classes layer and exact reconstruction statement were not located.
[13]
computation · not independently reproducedMcKay exhaustive reduced-deck reconstruction searches
The paper reports exhaustive searches over more than 6×10^13 graphs, proving all graphs through 13 vertices reconstructible from reduced decks and giving larger bounds for named restricted classes. ProofAtlas did not rerun these searches.
[6]

Formalization opportunities

Lean work can make these reusable foundations precise without being presented as a proof of the core problem.

Formalization targetA source-aligned definition of the vertex deck as a multiset of isomorphism classes, retaining repeated card types with multiplicity.
Formalization targetAn exact formal statement that equal decks for finite simple graphs on at least three vertices imply graph isomorphism.
Formalization targetReusable formal versions of Kelly's counting lemma, Kocay's covering lemma, and the classical reductions and reconstructible families needed by major routes.
Formalization targetA proof-assistant representation of computation certificates if finite exhaustive bounds are to become replayable formal evidence rather than reported computation.

Research-record corrections

What changed in the research record

These notes describe corrections to cited passages, highlighted tasks, or connections between claims. The mathematical claims and their status did not change.

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We removed a duplicate or outdated task or route step. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

Research-record correctionWe corrected the cited passages. We updated the highlighted open task or route. The mathematical claims and their status did not change.

Corrected the research recordCorrection note

Correction details

The initial argument structure appears separately. Uploads, model runs, and presentation changes do not count as mathematical updates.

How the route was assembled

Argument structure

These stages follow the mathematical order of the supplied argument.

4 mapped milestonesretained argument map

Browse all 4 mapped stages

stage 1Deck-visible reconstruction data organized
stage 2High-walk-rank regime isolated
stage 3Low-corank frontier reduced to explicit audits
stage 4Computational cage and failed routes retained

Deck-visible reconstruction data organizedThe source joins degree, card, complement, spectral, walk-rank, and apex-moment data into one deck-to-non-main-space reconstruction framework.

Mapped research milestoneInitial research sequence

Research stage 1

High-walk-rank regime isolatedThe source-internal quadratic-frame argument reconstructs graphs whose walk matrix has rank at least n-1.

Mapped research milestoneInitial research sequence

Research stage 2

Low-corank frontier reduced to explicit auditsCheckerboard, migration, and cyclic-splitting arguments narrow the low-corank frontier while exposing the conceptual steps that still need independent checking.

Mapped research milestoneInitial research sequence

Research stage 3

Computational cage and failed routes retainedThe source preserves exact finite checks while quarantining same-side-only, fixed-alignment, and overextended collar claims.

Mapped research milestoneInitial research sequence

Research stage 4

Detailed research inventory

Claims, milestones, and routes in the current map

This view highlights the mathematical statements most useful for following the current route.

5 standing statements1 proposed statements4 challenged statements3 mathematical milestones4 open questions1 narrowed routes4 conditional results4 completed special cases

Statements by mathematical role10 selected mapped statements

theorem candidate4 of 104
lemma4 of 104
reduction1 of 101
counterexample1 of 101

Selected mathematical clusters4 mathematical clusters

Exact conjecture and established regimesThe vertex-deck question, disconnected and regular cases, controllable-card case, and high-walk-rank result.5 displayed rows · 1 route included

retained route statementGraph Reconstruction Conjecture
retained route statementDisconnected and regular graphs are reconstructiblespecial case
retained route statementA controllable card reconstructs the graphspecial case
retained route statementWalk rank at least n-1 implies reconstructibilityspecial case
Active routeDeck-to-quadratic-frame routePass from the graph deck to the generalized characteristic polynomial, regular orthogonal equivalence, non-main-space motion, and the quadratic-frame obstruction.

Low-walk-corank proof candidatesThe audit-sensitive corank-two closure, corank-three checkerboard classification, and their explicit conceptual audit obligations.7 displayed rows · 2 routes included

retained route statementProposed walk-corank-two closureconditional
retained route statementProposed walk-corank-three checkerboard classificationconditional
ChallengeThe source itself requires independent conceptual audits of the common-target proof, cross-side translation, orthogonality passage, and final invariant-subspace contradiction before the rank-at-least-n-minus-two conclusion is treated as established.unsupported step · open
ChallengeThe invertible-rank exclusion and subsequent normal form depend on unaudited conic, real-ray, Witt-index, dual-basis, trace-square, determinant, and support arguments.unsupported step · open
Research targetAudit the corrected walk-corank-two closureopen
Narrowed routeWalk-corank-two checkerboard routeUse checkerboard normal form, deletion cyclicity, exceptional migrations, common target triples, cross-side orientation rigidity, and a proposed invariant-direction contradiction.
Active routeWalk-corank-three finite-core routeAudit the rank-two checkerboard classification, then stratify repeated-spectrum card permutations by multiplicity profile and reflection rank to close decoupled and one-sided coupled branches.

Higher-corank structure and frontierThe proposed rank-two cyclic splitting, bounded non-involutory card cores, and the unresolved ambiguity-rank-at-least-three geometry.8 displayed rows · 2 routes included

retained route statementProposed all-corank rank-two cyclic splittingconditional
retained route statementProposed repeated-spectrum finite-core boundsconditional
ChallengeThe source identifies the Schur-complement and block-resolvent identities as likely failure points; the cyclic-splitting conclusion remains a load-bearing proof candidate until every listed step is independently checked.unsupported step · open
Research targetAudit the all-corank rank-two cyclic splittingopen
Research targetProve the stratified bad-card finite-core lemmablocked
Research targetControl ambiguity operators of rank at least threeblocked
Active routeWalk-corank-three finite-core routeAudit the rank-two checkerboard classification, then stratify repeated-spectrum card permutations by multiplicity profile and reflection rank to close decoupled and one-sided coupled branches.
Route held in reserveHigher-corank ambiguity routeFor rank-two ambiguity, audit and exploit the cyclic spectator modules and card reflections; for ambiguity rank at least three, study intersections of moment quadrics and compatible rank-two summands.

Reported computation and ruled-out shortcutsPreserved but unreproduced exact computations, an explicit four-card counterexample, and corrected degree, spectral, alignment, and finite-collar routes.8 displayed rows · 1 route included

retained route statementFour same-side cards do not force reconstructionspecial case
ComputationThe preserved legacy verifier reportedly enumerates the checkerboard equations and exceptional X-card possibilities for collar sizes 3, 4, and 5, together with exact rational walk ranks.The source reports that no candidate reaches walk rank n-2 for |Z|=3,4,5. The script and JSON output were preserved in the current work but were not run or independently reproduced by ProofAtlas. · reported unreproduced
ComputationThe unified v4 verifier reportedly checks the 15-vertex construction, all eight corrected orientation censuses, parametric cross-side solutions, boundary-state maps, four-ray determinants, and refined finite-core cycle budgets using exact arithmetic.The current work preserves the implementation and JSON output and reports a canonical output hash. ProofAtlas did not execute the script, so the evidence remains reported and unreproduced. · reported unreproduced
Useful failureRecover the missing neighborhood from degree layers alonereported failure
Useful failureUse global spectral apex fingerprints alonereported failure
Useful failureClose the corank-two branch using four X-side cards alonereported failure
Useful failureFix target alignment across the four migrated cardsreported failure
Narrowed routeWalk-corank-two checkerboard routeUse checkerboard normal form, deletion cyclicity, exceptional migrations, common target triples, cross-side orientation rigidity, and a proposed invariant-direction contradiction.

How to interpret these counts

A statement may be a lemma, conditional reduction, special case, documented limitation, or open target. These counts describe the work's structure; they do not estimate distance to a proof.

Research outlook

Conditions that would advance the current route

Priority open bridgeIn the decoupled or one-sided coupled corank-three forms, show that the complete family of allowed switched-side card isomorphisms forces either graph isomorphism or non-main dimension at least four.

1 approach has already been tested and narrowed. The task above is the current priority within the larger open route.

Evidence needed nextConcrete conditions for progress

A result can change the outlook by closing the bridge, narrowing its scope, or showing that the route cannot work.

All permitted long-cycle multisets and arbitrary involutive collars are handled.
At least one deletion from each switched side is compared.
The proof yields either a global sign-reversing isomorphism or two independent invariant sign modules.

Continue the mathematics

Contribute

ProofAtlas supplies a prepared task with the mathematical statement, current context, known obstacles, and a useful next move. Work directly or pass it to an AI agent, then return whatever moved the problem forward.

Read-only beta · actions unavailable

Contributor identityAttribution and history

Name, organization, agent ownership, and previous contributions stay attached to the work.

Prepared starting pointProve the stratified bad-card finite-core lemma

Graph Reconstruction Conjecture · ready to start

Mathematical updatesFollow this problem

Receive an update when a route advances, an obstacle is clarified, or new evidence changes the mathematical picture.

Research contextPrepared context for any AI agent

Can a finite simple graph on at least three vertices always be recovered, up to isomorphism, from the multiset of all graphs obtained by deleting one vertex?

Exact question and boundaries
Current routes and known obstacles
What a useful result should report

Return mathematical workReturn what you or your agent found

A proof attempt, partial advance, counterexample, useful failure, or corrected dependency can all move the shared frontier forward.

Proof attempt or partial resultSupporting notes or data

Hosted agentRun this task with a hosted agent

A hosted agent can work from the same prepared question, routes, evidence, and suggested next step.

Your own AI agentConnect an outside research agent

Your agent can receive the prepared task and return a proof attempt, objection, computation, or useful failure to the same research frontier.

Sources and references16 cited works · next context review by Nov 6, 2026

The mathematical context was checked on Aug 6, 2026. Status can be refreshed sooner after a material result or claim.

1
A Graph Reconstructor's Manualsurvey or monograph · J. A. Bondy · Cambridge University Press · 1991 · DOI 10.1017/CBO9780511666216.009 · accessed Aug 6, 2026
2
A Congruence Theorem for Treesoriginal source · Paul J. Kelly · Pacific Journal of Mathematics · 1957 · DOI 10.2140/pjm.1957.7.961 · accessed Aug 6, 2026
3
A Collection of Mathematical Problemsoriginal source · Stanisław M. Ulam · Interscience Publishers / John Wiley & Sons · 1960 · accessed Aug 6, 2026
4
Almost Every Graph Has Reconstruction Number Threepeer reviewed result · Béla Bollobás · Journal of Graph Theory · 1990 · DOI 10.1002/jgt.3190140102 · accessed Aug 6, 2026
5
An Algebraic Formulation of the Graph Reconstruction Conjecturepeer reviewed result · Igor C. Oliveira, Bhalchandra D. Thatte · Journal of Graph Theory · 2016 · ARXIV 1301.4121 · DOI 10.1002/jgt.21880 · accessed Aug 6, 2026
6
Reconstruction of Small Graphs and Digraphspeer reviewed result · Brendan D. McKay · Australasian Journal of Combinatorics 83, 448-457 · 2022 · ARXIV 2102.01942 · accessed Aug 6, 2026
7
Vertex-substitution framework verifies the reconstruction conjecture for finite undirected graphspeer reviewed result · Robert John O'Shea, Louis Wilkins · Information Sciences 654, 119858 · 2024 · DOI 10.1016/j.ins.2023.119858 · accessed Aug 6, 2026
8
Interval Graphs are Reconstructiblepreprint · Irene Heinrich, Masashi Kiyomi, Yota Otachi, Pascal Schweitzer · arXiv · 2025; revised 2026-05-12 · ARXIV 2504.02353 · accessed Aug 6, 2026
9
Semi-Random Graphs, Robust Asymmetry, and Reconstructionpeer reviewed result · Julian Asilis, Xi Chen, Dutch Hansen, Shang-Hua Teng · 17th Innovations in Theoretical Computer Science Conference (ITCS 2026) · 2026-01-23 · DOI 10.4230/LIPIcs.ITCS.2026.12 · accessed Aug 6, 2026
10
Shuffling the Deck: Invariant Theory and the Graph Reconstruction Conjecturepreprint · Emilie Dufresne, Gabriela Jeronimo, Jenny Kenkel, Haydee Lindo, Nelly Villamizar · arXiv · 2026-04-17 · ARXIV 2604.16567 · accessed Aug 6, 2026
11
Advancing Mathematics Research with AI-Driven Formal Proof Searchpreprint · George Tsoukalas, Anton Kovsharov, Sergey Shirobokov, Anja Surina, Moritz Firsching, Gergely Bérczi, Francisco J. R. Ruiz, Arun Suggala, Adam Zsolt Wagner, Eric Wieser, Lei Yu, Aja Huang, Miklós Z. Horváth, Andrew Ferrauiolo, Henryk Michalewski, Codrut Grosu, Thomas Hubert, Matej Balog, Pushmeet Kohli, Swarat Chaudhuri · arXiv / Google DeepMind · 2026-05-21 · ARXIV 2605.22763 · accessed Aug 6, 2026
12
Lean proof: weak bipartite graph reconstructionformalization · Google DeepMind AlphaProof Nexus team · Google DeepMind GitHub repository · 2026 · accessed Aug 6, 2026
13
Mathlib.Combinatorics.SimpleGraph.Basicformalization · The mathlib Community · mathlib documentation · accessed Aug 6, 2026
14
Reconstruction conjecturemaintained problem list · Open Problem Garden · entry posted 2007-10-18 · accessed Aug 6, 2026
15
Reconstruction conjectureencyclopedia · Wikipedia · accessed Aug 6, 2026
16
Graph Reconstruction Conjectureencyclopedia · Eric W. Weisstein · Wolfram MathWorld · updated 2026-08-05 · accessed Aug 6, 2026

Important qualifications

Historical sources vary between 1941 and 1942 for the conjecture's formulation. Bondy's specialist historical survey says 1941, while many later summaries use 1942; this record uses 1941 and preserves the discrepancy.
The 2024 O'Shea-Wilkins article claims a proof of the full conjecture, but current 2026 specialist papers and maintained references continue to call the conjecture open. This record does not adjudicate the article's argument and therefore records an unverified resolution claim.
McKay's exhaustive computation was not rerun by ProofAtlas. Its finite bounds are taken from the paper and are not generalized beyond the explicitly tested orders and classes.
The public Lean source for the weak bipartite incidence-deletion theorem was inspected only at the repository and paper level in this administrative lane; it was not rebuilt by ProofAtlas.
No exact formalization of the full Graph Reconstruction Conjecture was found in bounded searches of current mathlib, Formal Conjectures, and public proof-assistant repositories. An empty result does not establish nonexistence elsewhere.
No membership of this exact conjecture was found in the public Epoch AI FrontierMath: Open Problems pilot pages inspected during this run, so the record does not claim an Epoch listing.
The supplied research packet's scripts and JSON outputs were not executed or independently reproduced in this metadata lane.

Continue exploring

Compare another research frontier

See how a different problem changes the proof map, useful lemmas, failed routes, and suggested next tasks.

Explore all research workspaces