# Reconstruction conjecture

Informally, the reconstruction conjecture in graph theory says that graphs are determined uniquely by their subgraphs. It is due to Kelly and Ulam.

Given a graph ${\displaystyle G=(V,E)}$, a vertex-deleted subgraph of ${\displaystyle G}$ is a subgraph formed by deleting exactly one vertex from ${\displaystyle G}$. Clearly, it is an induced subgraph of ${\displaystyle G}$.

For a graph ${\displaystyle G}$, the deck of G, denoted ${\displaystyle D(G)}$, is the multiset of all vertex-deleted subgraphs of ${\displaystyle G}$. Each graph in ${\displaystyle D(G)}$ 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:

Harary suggested a stronger version of the conjecture:

Given a graph ${\displaystyle G=(V,E)}$, an edge-deleted subgraph of ${\displaystyle G}$ is a subgraph formed by deleting exactly one edge from ${\displaystyle G}$.

## Related Topics

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mo invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag math invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag semantics invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mrow invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mstyle invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag mi invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389

Warning: DOMDocument::loadHTML(): Tag annotation invalid in Entity, line: 1 in /home/ashver/webapps/infospaze/index.php on line 389