| Reconstruction Conjecture |
Article Index for Reconstruction |
Shopping Reconstruction |
Website Links For Reconstruction |
Information AboutReconstruction Conjecture |
| CATEGORIES ABOUT RECONSTRUCTION CONJECTURE | |
| graph theory | |
| conjectures | |
|
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. This theorem has been proved for some specific classes of graphs, such as unlabeled Tree s. However, the conjecture remains open for arbitrary graphs. REFERENCES
|
|
|