Reconstruction conjecture

Importance: Outstanding ✭✭✭✭
Subject: Graph Theory
Keywords: reconstruction
Recomm. for undergrads: no
Posted by: zitterbewegung
on: October 18th, 2007

The \emph{deck} of a graph $G$ is the multiset consisting of all unlabelled subgraphs obtained from $G$ by deleting a vertex in all possible ways (counted according to multiplicity).

\begin{conjecture} If two graphs on $\ge 3$ vertices have the same deck, then they are isomorphic. \end{conjecture}

See Wikipedia's \href[Reconstruction Conjecture]{http://en.wikipedia.org/wiki/Reconstruction_conjecture} for more on this problem.

Bibliography

*[K] P. J. Kelly, A congruence theorem for trees, Pacific J. Math., 7 (1957), 961–968.

*[U] S. M. Ulam, A collection of mathematical problems, Wiley, New York, 1960.


* indicates original appearance(s) of problem.

A strategy for simple graphs?

How about 1) Prove for a 4-node, or tetrahedral graph. 2) Demonstrate that all graphs with > 4 nodes are composed of multiple overlapping tetrahedrons 3) Figure out how coupled tetrahedra function when nodes are deleted. 4) Induct on number of tetrahedra in graph. ?

Obviously (3) is the tough part, but why should it be impossible?

correction and partial results

this should be on 3 or more vertices. False for digraphs, hypergraphs, and infinite graphs. It is open for simple graphs and multigraphs

Question.

Does G have to be simple, or can it be a multigraph?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.