Formal Statements
Given a graph, a vertex-deleted subgraph of is a subgraph formed by deleting exactly one vertex from . Clearly, it is an induced subgraph of .
For a graph, the deck of G, denoted, is the multiset 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 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.
Read more about this topic: Reconstruction Conjecture
Famous quotes containing the words formal and/or statements:
“That anger can be expressed through words and non-destructive activities; that promises are intended to be kept; that cleanliness and good eating habits are aspects of self-esteem; that compassion is an attribute to be prized—all these lessons are ones children can learn far more readily through the living example of their parents than they ever can through formal instruction.”
—Fred Rogers (20th century)
“Is it true or false that Belfast is north of London? That the galaxy is the shape of a fried egg? That Beethoven was a drunkard? That Wellington won the battle of Waterloo? There are various degrees and dimensions of success in making statements: the statements fit the facts always more or less loosely, in different ways on different occasions for different intents and purposes.”
—J.L. (John Langshaw)