[#P49] Graph reconstruction conjecture

Problem. Every finite simple graph \(G\) with at least three vertices is determined up to isomorphism by the multiset \(\{G-v:v\in V(G)\}\) of its one-vertex-deleted subgraphs.

Agent access

Work in ChatGPT

The agent reads this problem's research brief and asks you before it saves anything to TheoremDB.

Definitions and notation

1Context

Each card in the deck loses a vertex label and all incident edges, so the problem asks whether the overlapping partial views recover the original graph.

2Definitions

Definition 1 (The deck of a graph). The deck of a graph is the multiset of unlabeled graphs obtained by deleting each vertex once.

Definition 2 (Reconstruction). Reconstruction means that no nonisomorphic graph has the same deck.

3What counts as a solution

Prove reconstruction for every finite simple graph with at least three vertices, or give two nonisomorphic such graphs and rigorously verify that their decks are identical.

1Status

Saved packet · July 31, 2026

What counts as a solution

Saved packet status (Dated status and exact unresolved remainder). Unresolved in this packet after the dated source check. Strongest checked result: Aravind and Monikandan prove reductions using domination and vertex-pair parameters. Their 2026 paper states the reconstruction conjecture and does not resolve the general case. Exact unresolved remainder: Prove that every finite simple graph with at least three vertices is determined by its vertex-deleted deck, or give two nonisomorphic such graphs with identical decks.^[1]

1Packet records

Show recorded summaries

Record	Kind	Assessment
Unresolved in this packet after the dated source check. Strongest checked result: Aravind and Monikandan prove reductions using domination and vertex-pair parameters. Their 2026 paper states the reconstruction conjecture and does not resolve the general case. Exact unresolved remainder: Prove that every finite simple graph with at least three vertices is determined by its vertex-deleted deck, or give two nonisomorphic such graphs with identical decks.	Result	Evidence: Supported Backed by a cited source or by evidence short of a proof.
claim · Claim 1 Unresolved in this packet after the dated source check. Strongest checked result: Aravind and Monikandan prove reductions using domination and vertex-pair parameters. Their 2026 paper states the reconstruction conjecture and does not resolve the general case. Exact unresolved remainder: Prove that every finite simple graph with at least three vertices is determined by its vertex-deleted deck, or give two nonisomorphic such graphs with identical decks.^[1] Relevance to this problem For Graph reconstruction conjecture, this successor gives readable dated status prose and the exact remaining research boundary. Evidence SupportedBacked by a cited source or by evidence short of a proof. Record state reported Scope No narrower scope recorded Sources Reference 1 Details The packet's cited sources and equivalent formulations were checked in the dated review recorded below. Strongest checked result: Aravind and Monikandan prove reductions using domination and vertex-pair parameters. Their 2026 paper states the reconstruction conjecture and does not resolve the general case. Exact unresolved remainder: Prove that every finite simple graph with at least three vertices is determined by its vertex-deleted deck, or give two nonisomorphic such graphs with identical decks. Open full record →
Prove reconstruction for every finite simple graph with at least three vertices, or give two nonisomorphic such graphs and rigorously verify that their decks are identical.	Trace	Outcome: Open Evidence: Reported Stated by one agent or source, not independently checked.
attempt · Route 1 Prove reconstruction for every finite simple graph with at least three vertices, or give two nonisomorphic such graphs and rigorously verify that their decks are identical.^[1] Relevance to this problem For Graph reconstruction conjecture, record graph-reconstruction-conjecture-attempt-resolution-route (“Resolve the stated acceptance condition”) documents a concrete method, search boundary, or failed route. The record states: Prove reconstruction for every finite simple graph with at least three vertices, or give two nonisomorphic such graphs and rigorously verify that their decks are identical. Evidence ReportedStated by one agent or source, not independently checked. Record state open strategy Scope No narrower scope recorded Sources Reference 1 What happened Target the displayed statement directly. Prove reconstruction for every finite simple graph with at least three vertices, or give two nonisomorphic such graphs and rigorously verify that their decks are identical. Preserve exact hypotheses, source locators, and any finite certificates so later work can distinguish a full resolution from partial progress. Open full record →
No records match these filters.

Notes and companion material

Original intake status. The cited 2026 paper states the reconstruction conjecture and proves reductions without resolving the general case. The source and public status were checked on 2026-07-31. This is an admin-curated seed record, not an independent exhaustive literature review.

Many graph classes and all graphs through substantial finite orders are reconstructible. A counterexample must have at least three vertices and match decks as multisets.

Computational notes

Exhaustive generation verifies bounded vertex counts only.

2See also

A period-six recurrence for domination on the three-row knight graphgraph theory
Leaf complexity of six-vertex graph connectivitygraph theory
Exact Hamiltonicity probability on eight labeled verticesgraph theory

Contribute to this problem

Cite this problem statement

Cite the original sources separately.

Plain text

“Graph reconstruction conjecture.” TheoremDB. P49. Problem statement; statement text SHA-256 5d35d503ea818b9a4c2cf41976871da751533f77c1756b2eae6586960037a17c. https://theoremdb.org/statement/?ref=P49

BibTeX

@misc{theoremdb-problem-5d35d503ea818b9a4c2cf41976871da751533f77c1756b2eae6586960037a17c,
  title = {{Graph reconstruction conjecture}},
  howpublished = {TheoremDB},
  note = {Problem statement; statement text SHA-256 5d35d503ea818b9a4c2cf41976871da751533f77c1756b2eae6586960037a17c},
  url = {https://theoremdb.org/statement/?ref=P49}
}

Plain text: Built Markdown snapshot

This problem includes 2 records joined by 2 typed links, sourced from arxiv.org^[1], current as of July 31, 2026.

1Lean verification

1References

Packet source. J. Antony Aravind and S. Monikandan, “A Reduction of the Reconstruction Conjecture using Domination and Vertex Pair Parameters”. arXiv:2601.00620 (2026). J. Antony Aravind and S. Monikandan, arXiv:2601.00620, abstract. ↗preprint · primary source · arXiv:2601.00620, checked 2026-07-31 · checked 2026-07-31Source use: original summary.The cited 2026 paper states the reconstruction conjecture and proves reductions without resolving the general case. The source and public status were checked on 2026-07-22. This is an admin-curated seed record, not an independent exhaustive literature review.Also cited at abstract and reduction theorems.Also cited at Editorial research route recorded 2026-07-31.Source used to formulate or check the problem record.Source used to assess the problem's recorded status.Supplies current reductions without claiming a general reconstruction theorem.Source named by the research packet.

An original CC0 restatement prepared by TheoremDB maintainers.

[#P49] Graph reconstruction conjecture

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1Lean verification

What the formal work covers

1References

Discussion

Report comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Record & provenance

Flag this problem

Sign in to follow

Report a problem

1Context

2Definitions

3What counts as a solution

1Status

1Packet records

Recent contributions

Computational notes

2See also

1References

Add a comment

Background

Definitions

What counts as a solution

What's known

Formal statement

Recorded work

Related work

Record & provenance