# P49: Graph reconstruction conjecture - ID: `P49` - Reference: `graph-reconstruction-conjecture` - Page: https://theoremdb.org/statements/P49 - Record maturity: Reviewed problem with recorded work ## 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. ### Context 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. ### Problem setup - **Definition (The deck of a graph).** The deck of a graph is the multiset of unlabeled graphs obtained by deleting each vertex once. - **Definition (Reconstruction).** Reconstruction means that no nonisomorphic graph has the same deck. - **Remark.** 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. ### What 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. ## Status 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](#reference-1) ## Work ### Evidence for the current status **Claim 1 (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. 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. ### Background and intake notes - 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-22. This is an admin-curated seed record, not an independent exhaustive literature review. - The formulation and status were checked against the cited paper on 2026-07-22. - 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. ### Open directions - **Route 1** (reported): 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](#reference-1) ### Computational notes - Exhaustive generation verifies bounded vertex counts only. ### Working on this Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `graph-reconstruction-conjecture`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome. ## References 1. 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 https://arxiv.org/abs/2601.00620 - Also cited at abstract and reduction theorems - Also cited at Editorial research route recorded 2026-07-31 - preprint; primary source; arXiv:2601.00620, checked 2026-07-31; checked 2026-07-31 - Source 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. - 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.