In graph theory, the reconstruction conjecture says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
StatementAny two hypomorphic graphs (graphs sharing the same multiset of vertex-deleted subgraphs, called the deck) on at least three vertices are isomorphic; attributed to Kelly and Ulam. 1 Progress Toward ResolutionVerified computationally for all graphs with at most thirteen vertices by Brendan McKay, and proved for several infinite families including regular graphs, trees, and disconnected graphs; no general proof exists. 1 Classification
Resolution Status Prize Status
Prize Status (category) Connections
In Branch
Source Reconstruction Conjecture (Wikipedia)
Posed By
Source Reconstruction Conjecture (Wikipedia)
Sources
1. Reconstruction Conjecture (Wikipedia)
Wikimedia FoundationLead section
informally, the reconstruction conjecture says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam
Formal statements section
Reconstruction Conjecture: Any two hypomorphic graphs on at least three vertices are isomorphic.
Verification section
Both the reconstruction and set reconstruction conjectures have been verified for all graphs with at most 13 vertices by Brendan McKay.
Infobox, unsolved problem statement
Are graphs uniquely determined by their subgraphs?
In Branch: Graph Theory, Lead sentence
In graph theory, informally, the reconstruction conjecture says that graphs are determined uniquely by their subgraphs.
Posed By: Stanislaw Ulam, Lead paragraph
It is due to Kelly and Ulam
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.