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