Reconstructing trees from two cards

Let be the class of unlabeled trees. An unlabeled vertex‐deleted subgraph of a tree T is called a card. A collection of cards is called a deck. We say that the tree T has a deck D if each card in D can be obtained by deleting distinct vertices of T . If T is the only unlabeled tree that has the deck D , we say that T is ‐reconstructible from D . We want to know how large of a deck D is necessary for T to be ‐reconstructible. We define rn( T ) as the minimum number of cards in a deck D such that T is ‐reconstructible from D . It is known that rn( T )≤3, but it is conjectured that rn( T )≤2 for all trees T . We prove that the conjecture holds for all homeomorphically irreducible trees. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 243–257, 2010