page_title: Reconstruction conjecture
section_title: Formal statements
hierarchical_section_title: Reconstruction conjecture / Formal statements
caption_attribution_description: English: A graph and its deck as described in the Reconstruction_conjecture of graph theory
context_page_description: Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.
context_section_description: Given a graph , a vertex-deleted subgraph of  is a subgraph formed by deleting exactly one vertex from . By definition, it is an induced subgraph of .
  For a graph , the deck of G, denoted , is the multiset of isomorphism classes of all vertex-deleted subgraphs of .  Each graph in  is called a card.  Two graphs that have the same deck are said to be hypomorphic.
  With these definitions, the conjecture can be stated as:
  Reconstruction Conjecture: Any two hypomorphic graphs on at least three vertices are isomorphic.
  (The requirement that the graphs have at least three vertices is necessary because both graphs on two vertices have the same decks.)
  Harary suggested a stronger version of the conjecture:
  Set Reconstruction Conjecture: Any two graphs on at least four vertices with the same sets of vertex-deleted subgraphs are isomorphic.
  Given a graph , an edge-deleted subgraph of  is a subgraph formed by deleting exactly one edge from .
  For a graph , the edge-deck of G, denoted , is the multiset of all isomorphism classes of edge-deleted subgraphs of .  Each graph in  is called an edge-card.
  Edge Reconstruction Conjecture: (Harary, 1964) Any two graphs with at least four edges and having the same edge-decks are isomorphic.
caption: A graph and the associated deck of single-vertex-deleted subgraphs. Note some of the cards show isomorphic graphs.
exif: {"Image ExifOffset": "26", "EXIF ExifImageWidth": "693", "EXIF ExifImageLength": "311"}