Informally, the
reconstruction problem is about the following. Consider a finite
graph
G with
vertices v_{1},...,
v_{n}. If someone
gives you a deck of cards which shows all the
subgraphs[?] where one vertex is deleted, ie the graphs
G-v_{i} for all
i, can you then find the original
graph
G? For graphs on two vertices this fails. Indeed, there are exactly
two graphs on two vertices, the single edge and two isolated
vertices, each of which
leads to the same deck of cards, namely to two cards showing each a
single vertex. However, for graphs with at least three vertices it has been conjectured
in 1942 by P. J. Kelly and
S. M. Ulam
that it is always possible to reconstruct the graph from its deck of cards.
More formally, the reconstruction conjecture states:
Let G and H be finite graphs with at least three vertices, and let there be
a bijection σ:V(G) → V(H) such that G-v is
isomorphic to H-σ(v) for every v ∈ V(G).
Then G and H are isomorphic.
Though there are several partial results, the conjecture remains open.
References:
- Nash-Williams, C.St.J.A., The Reconstruction Problem, Selected topics in graph theory, 205-236 (1978)
All Wikipedia text
is available under the
terms of the GNU Free Documentation License