# Trees with at least $6\ell+11$ vertices are $\ell$-reconstructible

Alexandr V. Kostochka , Mina Nahvi , Douglas B. West , Dara Zirlin University
of Illinois, Urbana IL, and Sobolev Institute of Mathematics, Novosibirsk,
Russia<EMAIL_ADDRESS>Supported by NSF grant DMS-2153507 and NSF RTG
grant DMS-1937241.University of Illinois, Urbana IL:
<EMAIL_ADDRESS>Normal Univ., Jinhua, China and Univ. of
Illinois, Urbana IL<EMAIL_ADDRESS>Supported by National Natural Science
Foundation of China grants NSFC 11871439, 11971439, and U20A2068.University of
Illinois at Urbana–Champaign, Urbana IL 61801<EMAIL_ADDRESS>Supported
in part by Arnold O. Beckman Campus Research Board Award RB20003 of the
University of Illinois.

###### Abstract

The $(n-\ell)$-deck of an $n$-vertex graph is the multiset of (unlabeled)
subgraphs obtained from it by deleting $\ell$ vertices. An $n$-vertex graph is
$\ell$-reconstructible if it is determined by its $(n-\ell)$-deck, meaning
that no other graph has the same deck. We prove that every tree with at least
$6\ell+11$ vertices is $\ell$-reconstructible.

##  1 Introduction

The $j$-deck of a graph is the multiset of its $j$-vertex induced subgraphs.
We write this as the $(n-\ell)$-deck when the graph has $n$ vertices and the
focus is on deleting $\ell$ vertices. An $n$-vertex graph is
$\ell$-reconstructible if it is determined by its $(n-\ell)$-deck. Since every
member of the $(j-1)$-deck arises $n-j+1$ times by deleting a vertex from a
member of the $j$-deck, the $j$-deck of a graph determines its $(j-1)$-deck.
Therefore, a natural reconstruction problem is to find for each graph the
maximum $\ell$ such that it is $\ell$-reconstructible. For this problem,
Manvel [11, 12] extended the classical Reconstruction Conjecture of Kelly [6]
and Ulam [17].

######  Conjecture 1.1 (Manvel [11, 12]).

For $l\in{\mathbb{N}}$, there exists a threshold $M_{\ell}$ such that every
graph with at least $M_{\ell}$ vertices is $\ell$-reconstructible.

Manvel named this “Kelly’s Conjecture” in honor of the final sentence in Kelly
[7], which suggested that one can study reconstruction from the $(n-2)$-deck.
Manvel noted that Kelly may have expected the statement to be false.

The classical Reconstruction Conjecture is $M_{1}=3$. Lacking a proof of
Conjecture 1.1 for any fixed $\ell$, we study threshold numbers of vertices
for $\ell$-reconstructibility of graphs in special classes. The survey by
Kostochka and West [8] describes prior such results. Here our aim is to reduce
the threshold number of vertices to guarantee $\ell$-reconstructibility of
trees.

Reconstruction arguments for special families have two parts, named (when
$\ell=1$) by Bondy and Hemminger [1]. When the $(n-\ell)$-deck guarantees that
all reconstructions or no reconstructions lie in the specified family, the
family is $\ell$-recognizable. Separately, using the knowledge that every
reconstruction from the deck is in the family, one determines that only one
graph in the family has that deck; this makes the family weakly
$\ell$-reconstructible. Together, the two steps make graphs in the family
$\ell$-reconstructible.

Nýdl [14] conjectured that trees with at least $2\ell+1$ vertices are weakly
$\ell$-reconstructible, having presented in [13] two trees with $2\ell$
vertices having the same $\ell$-deck, to make the conjecture sharp. The two
trees arise from a path with $2\ell-1$ vertices by adding one leaf, adjacent
either to the central vertex of the path or to one of its neighbors. Kostochka
and West [8] used the results of Spinoza and West [15] to give a short proof
of Nýdl’s result.

When $\ell=2$, the disjoint union of a $4$-cycle and an isolated vertex has
the same deck as these two trees, so $5$-vertex trees are not a
$2$-recognizable family. However, Kostochka, Nahvi, West, and Zirlin [10]
proved that $n$-vertex acyclic graphs are $\ell$-recognizable when $n\geq
2\ell+1$, except for $(n,\ell)=(5,2)$. As noted earlier, the $(n-\ell)$-deck
yields the $k$-deck whenever $k<n-\ell$, so the $(n-\ell)$-deck also yields
the $2$-deck, which fixes the number of edges. An $n$-vertex graph is a tree
if and only if it is acyclic and has $n-1$ edges, so the family of $n$-vertex
trees is $\ell$-recognizable when $n\geq 2\ell+1$ (except for
$(n,\ell)=(5,2)$).

This suggests modifying Nýdl’s conjecture to say that trees with at least
$2\ell+1$ vertices are $\ell$-reconstructible (modifying to $2\ell+2$ when
$\ell=2$). Indeed, Kelly [7] proved that trees with at least three vertices
are $1$-reconstructible, and Giles [2] proved that trees with at least six
vertices are $2$-reconstructible. Hunter [5] proved that caterpillars with at
least $(2+o(1))\ell$ vertices are $\ell$-reconstructible. Groenland, Johnston,
Scott, and Tan [4] found one counterexample to Nýdl’s conjecture for $\ell=6$:
two specific trees with $13$ vertices having the same $7$-deck. However, they
proved that a threshold number of vertices does exist for trees:

######  Theorem 1.2 ([4]).

When $j\geq{\frac{8}{9}n+\frac{4}{9}\sqrt{8n+5}+1}$, every $n$-vertex tree is
determined by its $j$-deck. Thus $n$-vertex trees are $\ell$-reconstructible
when $n\geq 9\ell+24\sqrt{2\ell}+o(\sqrt{\ell})$.

For $\ell=3$, this theorem applies when $n\geq 194$. Using reconstruction of
rooted trees, Kostochka, Nahvi, West, and Zirlin [9] gave a lengthy proof of
the threshold $n\geq 25$ when $\ell=3$. Our aim in this paper is to lower the
general threshold for $\ell$-reconstructibility of trees by proving the
following theorem, which brings the threshold for $\ell=3$ down to $n\geq 28$.

######  Theorem 1.3.

When $n\geq 6\ell+11$, all $n$-vertex trees are $\ell$-reconstructible.

We close this introduction by describing the structure of the paper. Our proof
is constructive; that is, we show how to obtain the unique $n$-vertex tree
corresponding to a given $(n-\ell)$-deck ${\mathcal{D}}$. As noted earlier,
the family of $n$-vertex trees is $\ell$-recognizable when $n\geq 2\ell+1$
[10], so we may assume that all reconstructions from ${\mathcal{D}}$ are
trees.

We divide the proof into various cases depending on whether the diameter of
the tree is high or low and on whether various special structures are present
in the tree. It is important to note that we must show each case is
recognizable from the deck before we can make use of the hypotheses of that
case in reconstructing the tree.

In Section 2, we develop tools used in various cases. We first show that
several important parameters of $T$ are $\ell$-reconstructible, including the
diameter (which we write as $r+1$), a number $k$ that is within $1$ of the
minimum radius among connected cards, and the number of vertices in $T$ from
which three edge-dispoint paths of length $\ell+1$ can be grown. We call such
vertices “spi-centers”, because a union of edge-disjoint paths with a common
endpoint is often called a spider. We also introduce a counting process called
an Exclusion Argument, which is a technique used repeatedly in later sections
to obtain various subtrees in $T$.

Sections 3–5 discuss the “high-diameter” case, defined by $r\geq n-3\ell$. In
this case, $k\geq\ell+1$, and the cards show all connected subgraphs of $T$
with diameter “not too large”. Section 3 completes the case where $T$ has a
spi-center, and Sections 4–5 consider the high-diameter trees without spi-
centers. In addition to spi-centers, we consider whether the deck has a sparse
card, which is a card containing an $r$-vertex path along which the card has
only one branch vertex. In Section 4, we find the maximal subtrees of diameter
$2k-2$ that contain the end portions of every $r$-vertex path in $T$. In
Section 5, we finish reconstructing $T$ by assembling these two subtrees
properly and finding the rest of the tree.

In Section 6, we consider the “small-diameter” case, meaning $r<n-3\ell$.
Subcases consider whether $T$ has a sparse card or not, whether the branch
vertex along the $r$-vertex path in a sparse card has degree $3$ or higher,
and whether $T$ has various other cards in which there is a long path from a
leaf to the nearest branch vertex. Note that the existence of various kinds of
cards is immediately recognizable from the deck.

##  2 Vines and Diameter

In studying $\ell$-reconstructibility of $n$-vertex trees, we use different
methods for trees with large diameter and trees with small diameter. Along the
way, we introduce various structures in trees whose presence or absence is
determined by the $(n-\ell)$-deck, and we use their occurrence or non-
occurrence in resolving various cases.

######  Definition 2.1.

In a graph $G$, the distance between two vertices is the minimum length of a
path containing them. The eccentricity of a vertex in a graph $G$ is the
maximum of the distances from it to other vertices. A center of $G$ is a
vertex of minimum eccentricity, and the minimum eccentricity is called the
radius of $G$. The diameter of $G$ is the maximum eccentricity, which is the
maximum distance between vertices.

It is an elementary exercise that a tree has one center or two adjacent
centers, when the diameter is even or odd, respectively. The deck of an
$n$-vertex tree has no cards that are paths precisely when the tree has no
paths with $n-\ell$ vertices. We then know the diameter, because we all paths
appear in the cards. Later in this section we will determine the diameter from
the deck also when it is larger. We will need to count subtrees with various
diameters, a technique we used in [10] in the more general situation of
$n$-vertex graphs whose $(n-\ell)$-decks have no cards containing cycles.

######  Definition 2.2.

A $j$-vine is a tree with diameter $2j$. A $j$-evine is a tree with diameter
$2j+1$. A $j$-center or $j$-central edge is the central vertex or edge in a
$j$-vine or $j$-evine, respectively.

######  Lemma 2.3.

In a tree $T$, every $j$-vine or $j$-evine $H$ lies in a unique maximal
$j$-vine or $j$-evine, respectively.

###### Proof.

The unique maximal such graph containing $H$ is the subgraph induced by the
set of all vertices within distance $j$ of its central vertex or central edge.
This is a $j$-vine or $j$-evine, respectively. Any other such subgraph
containing it would have to have the same center or central edge, but then it
cannot have any additional vertices. $\Box$

For a family ${\mathcal{F}}$ of graphs, an ${\mathcal{F}}$-subgraph of a graph
$G$ is an induced subgraph of $G$ belonging to ${\mathcal{F}}$. For
$F\in{\mathcal{F}}$, let $m(F,G)$ be the number of copies of $F$ that are
maximal ${\mathcal{F}}$-subgraphs in $G$. The case $\ell=1$ of the next lemma
is due to Greenwell and Hemminger [3]. Similar statements for general $\ell$
appear for example in [4]. We include a proof for completeness; it is slightly
simpler than proofs in the literature involving inclusion chains.

######  Lemma 2.4 ([10]).

Let ${\mathcal{F}}$ be a family of graphs such that every subgraph of $G$
belonging to ${\mathcal{F}}$ lies in a unique maximal subgraph of $G$
belonging to ${\mathcal{F}}$. If for every $F\in{\mathcal{F}}$ with at least
$n-\ell$ vertices the value of $m(F,G)$ is known from the $(n-\ell)$-deck of
$G$, then for all $F\in{\mathcal{F}}$ the $(n-\ell)$-deck ${\mathcal{D}}$
determines $m(F,G)$.

###### Proof.

Let $t=\left|V(G)\right|-\left|V(F)\right|$; we use induction on $t$. When
$t\leq\ell$, the value $m(F,G)$ is given. When $t>\ell$, group the induced
subgraphs of $G$ isomorphic to $F$ according to the unique maximal
${\mathcal{F}}$-subgraph of $G$ containing them (as an induced subgraph).
Counting all copies of $F$ then yields

$s(F,G)=\sum_{H\in{{\mathcal{F}}}}s(F,H)m(H,G).$

Since $\left|V(F)\right|<n-\ell$, we know $s(F,G)$ from the deck, and we know
$s(F,H)$ when $F$ and $H$ are known. By the induction hypothesis, we know all
values of the form $m(H,G)$ when $F$ is an induced subgraph of $H$ except
$m(F,G)$. Therefore, we can solve for $m(F,G)$. $\Box$

Next we establish consistent notation for our subsequent discussion.

######  Definition 2.5.

Always ${\mathcal{D}}$ denotes the $(n-\ell)$-deck of an $n$-vertex tree $T$;
we call ${\mathcal{D}}$ simply the deck of $T$. Also $r$ denotes always the
maximum number of vertices in a path in $T$. A connected subcard or simply
subcard of $T$ is a connected subgraph of $T$ with at most $n-\ell$ vertices;
it appears in a connected card. We use “csc” for “connected subcard”.

######  Definition 2.6.

Fix $k$ to be the largest integer $j$ such that $T$ contains a $j$-evine and
every $j$-evine in $T$ has fewer than $n-\ell$ vertices. This fixes $k$ for
the remainder of the paper.

######  Lemma 2.7.

The value of $k$ is determined by the deck of $T$.

###### Proof.

Each edge forms a $0$-evine (which are the only $0$-evines), and every
$j$-evine with $j>0$ contains a smaller $(j-1)$-evine, so the value of $k$ is
well-defined. It remains to compute $k$.

All subgraphs with at most $n-\ell$ vertices are visible from the deck. The
deck yields a largest value $j^{\prime}$ such that some csc is a
$j^{\prime}$-evine and all such cscs have fewer than $n-\ell$ vertices. Since
$k$ is an integer having these properties, $j^{\prime}\geq k$. Since some csc
is a $j^{\prime}$-evine with fewer than $n-\ell$ vertices,
$2j^{\prime}+2<n-\ell$.

By the choice of $j^{\prime}$, no $j^{\prime}$-evine in $T$ has exactly
$n-\ell$ vertices, so a smallest $j^{\prime}$-evine with more than $n-\ell$
vertices can only be a path, which would require $2j^{\prime}+2>n-\ell$. Thus
no such $j^{\prime}$-evine exists, yielding $k\geq j^{\prime}$. Hence
$j^{\prime}=k$. $\Box$

######  Lemma 2.8.

In a reconstruction $T$ from ${\mathcal{D}}$, there exist $k$-vines, and every
$k$-vine in $T$ has fewer than $n-\ell$ vertices.

###### Proof.

By the definition of $k$, there is a $k$-evine in $T$. A $k$-evine contains
two $k$-vines whose centers form the central edge of the $k$-evine.

If some $k$-vine has at least $n-\ell$ vertices, then let $C$ with center $z$
be a largest $k$-vine in $T$. Since $T$ contains a $k$-evine, the diameter of
$T$ is at least $2k+1$, and hence the radius of $T$ is at least $k+1$. Thus
$T$ has a vertex $x$ at distance $k+1$ from $z$. Note that $x$ is not
contained in $C$, but $x$ has a neighbor $y$ in $C$ at distance $k$ from $z$.
Adding $x$ and the edge $xy$ to $C$ creates a $k$-evine with more than
$n-\ell$ vertices, contradicting the definition of $k$. $\Box$

######  Corollary 2.9.

For $j\leq k$, the deck ${\mathcal{D}}$ determines the numbers of maximal
$j$-evines and $j$-vines with each isomorphism type. All reconstructions from
${\mathcal{D}}$ have the same numbers of $j$-centers and $j$-central edges.

###### Proof.

Fix $j$, and let ${\mathcal{F}}$ be the family of $j$-vines or the family of
$j$-evines. By the definition of $k$ and Lemmas 2.7 and 2.8, $m(F,T)=0$ for
all $F\in{\mathcal{F}}$ having at least $n-\ell$ vertices. Hence Lemma 2.4
applies to compute $m(F,T)$ for all $F\in{\mathcal{F}}$. By Lemma 2.3, there
is a one-to-one correspondence between the maximal $j$-vines and the
$j$-centers, and similarly for $j$-evines and $j$-central edges. $\Box$

Since $1$-vines are stars, setting $j=1$ in Corollary 2.9 provides the degree
list if $k\geq 1$. Groenland et al. [4] proved that the degree list is
$\ell$-reconstructible for all $n$-vertex graphs whenever
$n-\ell>\sqrt{2n\log(2n)}$. Taylor [16] had shown that asymptotically
$n>\ell{\rm e}$ is enough. For trees we obtain a simpler intermediate
threshold that suffices for our needs.

######  Corollary 2.10.

For $n\geq 2\ell+3$, the degree list of any $n$-vertex tree is determined by
its $(n-\ell)$-deck.

###### Proof.

All $1$-vines are stars. Each vertex with degree at least $2$ is the center of
exactly one maximal $1$-vine. Suppose first that no star has at least $n-\ell$
vertices. For $t\geq 3$, by the counting argument (Lemma 2.4) the deck
determines the number of maximal $1$-vines having $t$ vertices. This is the
number of vertices with degree $t-1$ in any reconstruction.

Now suppose that some star has at least $n-\ell$ vertices. Since $n-\ell\geq
4$, we see in the deck that there are no $3$-cycles or $4$-cycles, so two
stars share at most a common leaf or an edge joining the centers. Having two
stars with at least $n-\ell$ vertices thus requires $n\leq 2\ell+2$.

Hence only one vertex has degree at least $n-\ell-1$. Its degree is $d$ if and
only if exactly $\binom{d}{n-\ell-1}$ cards are stars. Thus we have $m(S,T)$
for any reconstruction $T$ and every star $S$ with at least $n-\ell$ vertices.
Again Lemma 2.4 applies and we obtain the number of vertices with degree $t-1$
whenever $t\geq 3$.

Since every reconstruction is a tree, the remaining vertices have degree $1$.
$\Box$

######  Lemma 2.11.

Every connected card in ${\mathcal{D}}$ has diameter at least $2k+2$, and some
connected card has diameter at most $2k+3$.

###### Proof.

A connected card with diameter at most $2k+1$ would be a $j$-evine or $j$-vine
with $j\leq k$ having $n-\ell$ vertices, contradicting the definition of $k$
or Lemma 2.8.

For the second claim, let $C$ be a connected card. If $C$ has diameter at
least $2k+3$, then $C$ contains a path with $2k+4$ vertices. Hence $n-\ell\geq
2k+4$ and $T$ contains a $(k+1)$-evine. By the definition of $k$, some
$(k+1)$-evine has at least $n-\ell$ vertices. Since $n-\ell\geq 2k+4$, we can
iteratively delete leaves of such a $(k+1)$-evine outside a path with $2k+4$
vertices to trim the subtree to $n-\ell$ vertices. We thus obtain a card that
is a $(k+1)$-evine and has diameter $2k+3$. Hence some card has diameter at
most $2k+3$. $\Box$

In a tree $T$, the number $r$ of vertices in a longest path is the diameter
plus $1$.

######  Lemma 2.12.

$(r-3)/2\geq k\geq(r-\ell-4)/2$. In particular, if $r\geq 3\ell+6$, then
$k\geq\ell+1$.

###### Proof.

Lemma 2.11 guarantees a connected card with diameter at least $2k+2$. It
contains a path with at least $2k+3$ vertices, so $r\geq 2k+3$.

Let $P$ be a longest path in $T$. By Lemma 2.11, some connected card $C$ has
diameter at most $2k+3$. Since $T$ has no cycle and $C$ has no path with more
than $2k+4$ vertices, at most $2k+4$ vertices of $P$ appear in $C$. In
addition, $T$ has only $\ell$ vertices outside $C$. Hence $r\leq 2k+4+\ell$,
which yields the claimed lower bound on $k$.

When $r\geq 3\ell+6$, the lower bound on $k$ simplifies to $k\geq\ell+1$.
$\Box$

When $r<n-\ell$, the value of $r$ is the maximum number of vertices in a path
contained in a card. Next we show that the deck also determines $r$ when
$r\geq n-\ell$.

######  Lemma 2.13.

If $n\geq 4\ell+8$ and $r\geq n-\ell$, then $k\geq\ell+2$, all paths in $T$
with more than $n-r$ vertices intersect any longest path $P$, all $k$-centers
and $(k-1)$-centers in $T$ lie on $P$, and the value of $r$ is determined by
the deck.

###### Proof.

With $r\geq n-\ell$ and $n\geq 4\ell+8$, Lemma 2.12 yields
$k\geq(n-2\ell-4)/2\geq\ell+2$. All paths with more than $n-r$ vertices
intersect $P$, since only $n-r$ vertices exist outside $P$.

Since $\ell\geq n-r$, all paths with at least $\ell+1$ vertices intersect $P$.
Since also $k\geq\ell+2$, all paths with at least $k-1$ vertices intersect
$P$. From a vertex outside $P$, only one path leads to $P$; hence all
$k$-centers and $(k-1)$-centers lie on $P$.

Since $T$ has a $k$-vine, $r\geq 2k+1$, so $k$-centers (and $(k-1)$-centers)
do exist on $P$. When $2j+1\leq r$, all the vertices of $P$ are $j$-centers
except the $j$ vertices closest to each end. By Corollary 2.9, the deck
determines the number $s$ of $k$-centers. Hence $r=s+2k$. $\Box$

When $k\geq\ell+1$, it follows from Corollary 2.9 that we know the number of
$(\ell+1)$-centers in $T$. Furthermore, we know the multiset of maximal
$(\ell+1)$-vines in $T$. Among these, there is a particular type of
$(\ell+1)$-vine that figures heavily in our analysis.

######  Definition 2.14.

A branch vertex in a tree is a vertex having degree at least $3$. A leg in a
non-path tree is a path from a leaf to the nearest branch vertex. A spider is
a tree with at most one branch vertex; its degree is the degree of the branch
vertex. The spider $S_{j_{1},\ldots,j_{d}}$ with $1+\sum_{i=1}^{d}j_{i}$
vertices is the union of legs with lengths $j_{1},\ldots,j_{d}$ having a
common endpoint. A spi-center is an $(\ell+1)$-center that is the branch
vertex in a copy of $S_{\ell+1,\ell+1,\ell+1}$ in $T$. We will often discuss
$3$-legged spiders whose three legs have the same length. For this special
situation with legs of length $j$ we write $S^{j}$; that is,
$S^{\ell+1}=S_{\ell+1,\ell+1,\ell+1}$.

######  Corollary 2.15.

If $k\geq\ell+1$, then the deck determines the number of spi-centers in $T$.

###### Proof.

When $j\leq k$, by Corollary 2.9 we know all the maximal $j$-vines. The spi-
centers correspond bijectively to the maximal $(\ell+1)$-vines that contain
$S^{\ell+1}$. $\Box$

######  Lemma 2.16.

Suppose $n\geq 4\ell+1$ and $r<n-\ell$. If $T$ has a card $C$ that is a
$3$-legged spider, then $T$ has no spi-center other than the branch vertex of
$C$.

###### Proof.

A copy of $S^{\ell+1}$ with branch vertex other than $z$ would have a leg
completely outside $C$. Since $T$ has only $\ell$ vertices outside $C$, this
cannot occur. $\Box$

######  Definition 2.17.

In a tree $T$, an offshoot from a vertex set $S$ (or from the subgraph induced
by $S$) is a component of $T-S$, rooted at its vertex having a neighbor in
$S$. The length of an offshoot is the maximum number of vertices in a path in
it that begins at its root.

######  Lemma 2.18.

Let $P$ be a longest path in $T$, with vertices $v_{1},\ldots,v_{r}$. If
$v_{j}$ with $j\leq(r+1)/2$ is a spi-center and no vertex between $v_{j}$ and
$v_{r+1-j}$ is a spi-center, then all longest paths have
$v_{j},\ldots,v_{r+1-j}$ as their $r-2j+2$ central vertices.

###### Proof.

Since $v_{j}$ is a spi-center, $T$ has an offshoot from $P$ at $v_{j}$ with
length at least $\ell+1$. Since $P$ is a longest path, $\ell+1\leq j-1$.

All longest paths in a tree have the same central vertex (or vertex pair). If
a longest path $P^{\prime}$ diverges from $P$ at some vertex $w$ between
$v_{j}$ and $v_{r+1-j}$, then $P^{\prime}$ has at least $j$ vertices outside
$P$. Now $w$ is a spi-center, contradicting the hypothesis. $\Box$

We will often consider offshoots from a longest path $P$. The union of a
vertex $z$ on $P$ together with the offshoots from $P$ at $z$ is a rooted tree
with $z$ as root. The next lemma describes an exclusion argument that we use
in various situations to obtain offshoots at a vertex $z$ of a tree being
reconstructed.

######  Lemma 2.19 (The Exclusion Argument).

For a rooted tree $R$ with root $z$, the $z$-offshoots are the components of
the graph $R-z$, rooted at the neighbors of $z$. If the largest $z$-offshoots
of $R$ are known (with multiplicities), then the complete list of
$z$-offshoots is determined by the multiset $\cal M$ of all rooted subtrees
obtained from individual $z$-offshoots.

###### Proof.

The $z$-offshoots are determined in nonincreasing order of number of vertices.
The largest $z$-offshoots are given initially. Having determined all
$z$-offshoots with more than $p$ vertices, let $C$ be a rooted tree with $p$
vertices in $\cal M$. Since we know all $z$-offshoots of $R$ larger than $C$,
we know how many copies of $C$ in $\cal M$ arise from larger $z$-offshoots by
deleting some number of leaves. The number of copies of $C$ as a $z$-offshoot
is obtained from the number of copies of $C$ in $\cal M$ by excluding those
that arise from larger $z$-offshoots. $\Box$

##  3 Sparse Cards and $3$-Legged Spiders

As in Section 2, we keep $k$ defined as in Definition 2.6 and $r$ as the
maximum number of vertices in a path in the $n$-vertex tree $T$ that we want
to show is determined by its $(n-\ell)$-deck ${\mathcal{D}}$. In this section
we show that trees containing $S^{\ell+1}$ (that is, having a spi-center) are
$\ell$-reconstructible when their diameter and number of vertices are not
small. The presence of $S^{\ell+1}$ guarantees $r\geq 2\ell+3$, but the
stronger lower bound $r\geq 3\ell+6$ will guarantee $k\geq\ell+1$ (by Lemma
2.12). The lower bound $r\geq 3\ell+6$ is implied by $n\geq 6\ell+6$ and
$r\geq n-3\ell$. We first define additional terminology for structures used in
the proofs.

######  Definition 3.1.

An $r$-path is an $r$-vertex path; we use this term only for longest paths in
trees whose longest paths have $r$ vertices. In the $(n-\ell)$ deck of such a
tree, a long card is a connected card containing an $r$-path. Similarly, a
long csc or long subtree is a csc or subtree containing an $r$-path.

When $r<n-\ell$, a sparse card is a long card such that some $r$-path in the
card contains exactly one branch vertex of the card. That branch vertex is the
primary vertex of the card. The degree of a sparse card $C$ is the degree in
$C$ of its primary vertex. Note that an $r$-path omits at least one leg in any
copy of $S^{\ell+1}$, so $S^{\ell+1}\subseteq T$ implies $r<n-\ell$.

######  Lemma 3.2.

If $n\geq 6\ell+6$ and $r\geq n-3\ell$, and $T$ contains a sparse card and
exactly one spi-center, then $T$ is $\ell$-reconstructible.

###### Proof.

As noted before Definition 3.1, the hypotheses imply $r\geq 3\ell+6$, which
implies $k\geq\ell+1$. By Lemma 2.7, we know $k$, and then Corollary 2.15
gives us the number of spi-centers. By Lemma 2.13, we also know $r$. We see
all cards in the deck, so we see that $T$ has a sparse card. Thus we recognize
that $T$ has the specified properties. As noted in Definition 3.1,
$S^{\ell+1}\subseteq T$ implies $r<n-\ell$.

Let $C_{1}$ be a sparse card with $r$-path $P$ and primary vertex $z$. We
claim that this vertex $z$ is the unique spi-center in $T$. Otherwise, let $w$
be the vertex on $P$ closest to the spi-center. Since $P$ is a longest path,
the two portions of $P$ leaving $w$ are as long as any leg of $S^{\ell+1}$
that is not on $P$, which makes $w$ a spi-center. However, no vertex of $P$
other than $z$ can be a spi-center, since $C_{1}$ being a sparse card means
that at most $\ell$ vertices lie in offshoots from $P$ at vertices other than
$z$. Thus the unique spi-center is $z$ (see Figure 1).

Since we see $z$ in $C_{1}$, we may specify $j$ with $j\leq{(r+1)/2}$ by
saying that the distance of $z$ from the closest endpoint of $P$ is $j-1$.
Since $r\geq n-3\ell$, there are at most $2\ell$ vertices in offshoots from
$P$ at $z$. Thus no copy of $S^{\ell+1}$ has two legs outside $P$. This
implies $j-1\geq\ell+1$.

Figure 1: Sparse card $C_{1}$ and large csc $C_{2}$

Let $C_{2}$ be a largest long csc among those having an $r$-path $P^{\prime}$
with vertices $v_{1},\ldots,v_{r}$ such that
$d_{C_{2}}(v_{j})=d_{C_{2}}(v_{r+1-j})=2$. (see Figure 1). By Lemma 2.18,
every $r$-path in $T$ has $v_{j},\ldots,v_{r+1-j}$ as its central portion, so
$z\in\\{v_{j},v_{r+1-j}\\}$.

Since $z$ is a spi-center, we omit at least $\ell+1$ vertices in the offshoots
from $P^{\prime}$ at $z$, so $C_{2}$ has fewer than $n-\ell$ vertices. By its
maximality, $C_{2}$ contains in full all offshoots from $P^{\prime}$ at
vertices other than $v_{j}$ and $v_{r+1-j}$.

Let $T_{1}$ and $T_{2}$ be the components of $T-z$ containing the neighbors of
$z$ on $P^{\prime}$, with $T_{1}$ containing $j-1$ vertices from $P^{\prime}$.
If $j<(r+1)/2$, then let $z$ be the vertex of $\\{v_{j},v_{r+1-j}\\}$ other
than $z$; otherwise, let $z^{\prime}=z$. Let $W$ and $W^{\prime}$ be the
unions of the offshoots from $P^{\prime}$ in $T$ at $z$ and at $z^{\prime}$,
respectively. Thus $W^{\prime}\subseteq T_{2}$ if $j<(r+1)/2$, but
$W^{\prime}=W$ if $j=(r+1)/2$, in which case $T_{1}$ and $T_{2}$ are labeled
arbitrarily.

Claim: If $T_{1}$ and $T_{2}$ are known, then $T$ can be reconstructed from
the deck. Since $T_{2}$ contains $W^{\prime}$ when $j<(r+1)/2$, and
$W^{\prime}=W$ when $j=(r+1)/2$, it remains only to determine $W$. We know
$\left|V(W)\right|$, since we know the rest of the tree. If
$\left|V(W)\right|=\ell+1$, then $W$ is just a path and we know it, so we may
assume $\left|V(W)\right|>\ell+1$.

By Lemma 2.8, every $k$-vine in $T$ has fewer than $n-\ell$ vertices and hence
appears as a csc. Since $\ell+1\leq k$, this also holds for every
$(\ell+1)$-vine. Since $T$ has only one spi-center, there is a unique largest
$(\ell+1)$-vine containing $S^{\ell+1}$; it has center $z$. In this
$(\ell+1)$-vine we see all vertices at distance $\ell+1$ from $z$ in $T$; let
$n^{\prime}$ be the number of them.

Let ${\mathcal{C}}$ be the family of cscs consisting of a path with $2\ell+3$
vertices and offshoots from the center of the path, at least one of which has
length at least $\ell+1$. Every such csc contains $S^{\ell+1}$, and the branch
vertex of the copy of $S^{\ell+1}$ must always be $z$.

Since $r\geq 3\ell+3$, any csc in ${\mathcal{C}}$ in which two path legs of
length $\ell+1$ come from $T_{1}$ and $T_{2}$ omits at least $\ell$ vertices
of $P^{\prime}$ and hence is contained in a card. Some of these consist of $W$
plus $2\ell+3$ vertices from $P^{\prime}$; we will find such a csc.

Let $n_{0}$, $n_{1}$, and $n_{2}$ be the numbers of vertices at distance
$\ell+1$ from $z$ in $W$, $T_{1}$, and $T_{2}$, respectively. We know $n_{1}$
and $n_{2}$ from $T_{1}$ and $T_{2}$, and we compute
$n_{0}=n^{\prime}-n_{1}-n_{2}$. The number of cscs with
$2\ell+3+\left|V(W)\right|$ vertices having path legs in $W$ and $T_{2}$ is
$n_{0}n_{2}$ times the number of rooted subtrees of $T_{1}$ with
$\left|V(W)\right|$ vertices, and we know those subtrees. We similarly
eliminate the cscs having legs in $W$ and $T_{1}$. There are no members of
${\mathcal{C}}$ in which the two path legs of length $\ell+1$ come from $W$,
since $P^{\prime}$ has at least $n-3\ell$ vertices and this would give $C_{2}$
more than $n-\ell$ vertices. Since $\left|V(W)\right|>\ell+1$, we have
discarded cscs with $2\ell+3+\left|V(W)\right|$ vertices only once. The
remaining $n_{1}n_{2}$ members of ${\mathcal{C}}$ with
$2\ell+3+\left|V(W)\right|$ vertices show us $W$. This completes the proof of
the claim.

It therefore suffices to determine $T_{1}$ and $T_{2}$.

Case 1: $j<(r+1)/2$ and $C_{2}$ is asymmetric. By asymmetric, we mean that no
automorphism of $C_{2}$ reverses the indexing of $P^{\prime}$. That is, in
$C_{2}$ the vertices $v_{j}$ and $v_{r+1-j}$ are distinguishable, although we
do not yet know which is $z$.

Recall that $C_{2}$ has fewer than $n-\ell$ vertices. Consider augmentations
of $C_{2}$ obtained by adding a path leaving one of $\\{v_{j},v_{r+1-j}\\}$.
Let $m$ be the maximum $i$ such that we can obtain cscs by adding to $C_{2}$ a
path of $i$ vertices from either $v_{j}$ or $v_{r+1-j}$. Since $j-1\geq\ell+1$
and $z$ is the only spi-center in $T$, no offshoot from $z^{\prime}$ has
length at least $\ell+1$, so $m\leq\ell$. Since $T$ has a path of $\ell+1$
vertices grown from $P^{\prime}$ at $z$, we can tell which of
$\\{v_{j},v_{r+1-j}\\}$ is $z$ by considering trees obtained from $C_{2}$ by
growing a path of $m+1$ vertices from $v_{j}$ or $v_{r+1-j}$. The one that
exists as a csc fixes $z$, since $C_{2}$ is asymmetric. By reversing the
indexing of $C_{2}$ along $P^{\prime}$ if needed, we may now assume $z=v_{j}$.

Let $C_{3}$ be a largest subtree of $T$ containing $C_{2}$ in which $v_{j}$
has degree $2$. Since $C_{3}$ omits at least $\ell+1$ vertices in an offshoot
at $z$, we see all of $C_{3}$ in a card, and $C_{3}$ contains all offshoots
from $P^{\prime}$ at vertices other than $z$ in full. This determines $T_{1}$
and $T_{2}$, and the Claim applies to complete the reconstruction of $T$.

Case 2: $j<(r+1)/2$ and $C_{2}$ is symmetric. By the symmetry of $C_{2}$ we
may assume $z=v_{j}$, but we do not yet know the offshoots at $z$ (that is,
$W$) or at $z^{\prime}$ (that is, $W^{\prime}$).

Subcase 2a: $r+1-2j\leq\ell+1$. Let $t=\max\\{j,r-2j+1+\ell+1\\}$. Let $C_{4}$
be a largest subtree containing $S_{\ell+1,\ell+1,t}$ plus offshoots from the
spider at the vertex $w$ in the long leg having distance $r+1-2j$ from the
branch vertex. Since $\ell+1\leq j-1$, we have $j+t\leq r$, and hence $T$
contains $S_{\ell+1,\ell+1,t}$ with the long leg of the spider along
$P^{\prime}$. Thus $C_{4}$ exists.

Since $T$ has only one spi-center, the branch vertex of $S_{\ell+1,\ell+1,t}$
in $C_{4}$ is $z$. Since $t>j-1$ and $P^{\prime}$ is a longest path, the long
leg of the spider must extend along $P^{\prime}$ from $z$. Again since there
is only one spi-center, the leg cannot depart $P^{\prime}$ between $z$ and
$z^{\prime}$, so $w=z^{\prime}$. Since the leg extends at least $\ell+1$
vertices past $z^{\prime}$ and there are at most $\ell$ vertices in offshoots
from $P^{\prime}$ not at $z$, the leg must continue along $P^{\prime}$ past
$z^{\prime}$, and the offshoots from the spider at $w$ must lie in
$W^{\prime}$.

Since $W^{\prime}$ has at most $\ell$ vertices, and $r+1-2j\leq\ell+1$, we
have $t\leq\max\\{j,2\ell+2\\}$. Thus $C_{4}$ has at most
$\max\\{j+3\ell+3,5\ell+5$ vertices. If $j\leq 2\ell$, then since $n\geq
6\ell+5$, the tree $C_{4}$ fits in a card, and we see it in the deck. If
$j>2\ell$, then with $T_{1}$ containing from $C_{4}$ at most a short leg of
the spider, $C_{4}$ omits at least $\ell$ vertices from $T_{1}$ and again fits
in a card. By its maximality, $C_{4}$ shows us all of $W^{\prime}$. Now we
know $T_{1}$ and $T_{2}$, and the Claim applies to complete the reconstruction
of $T$.

Subcase 2b: $r+1-2j\geq\ell+2$. Let $C_{5}$ be a largest subtree containing
$S_{\ell+1,j-1,j}$ such that the end of the leg of length $j$ in the spider is
a leaf of $C_{5}$. Since $\ell+1\leq j-1$ and $T$ has only one spi-center, the
branch vertex of the required spider in $C_{5}$ must be $z$. All paths of
length at least $j$ from $z$ lie in $T_{2}$. Since $r-j\geq\ell+j+1$, the
subtree $C_{5}$ omits more than $\ell$ vertices from the end of $P^{\prime}$
and hence appears in a card. Whether the long leg of the spider in $C_{5}$
extends into $W^{\prime}$ or not, by its maximality $C_{5}$ shows us $T_{1}$
and all offshoots in $W$ (it is possible that $W$ has length $j-1$, making
$T_{1}$ and $W$ confusable, but we know them both).

From $C_{2}$, we know all of $T_{2}$ except $W^{\prime}$. Knowing $W$, we know
$\left|V(W)\right|$. Since we also know $C_{2}$, we know how many vertices
remain for $W^{\prime}$; let $m$ denote this value. Now consider subtrees of
$T$ containing an $r$-path $u_{1},\ldots,u_{r}$ such that $u_{j}$ has degree
$2$, the offshoots from $u_{r+1-j}$ total $m$ vertices, and the offshoots from
other vertices along the path total $n-m-\left|V(W)\right|$ vertices. Since
such subtrees with $u_{j}=v_{j}$ omit at least a path of $\ell+1$ vertices
from $W$, they fit in cards, so we see them. Since we know $W$, we know all
such subtrees in which $u_{r+1-j}=z$. Discarding them leaves a csc that shows
us $W^{\prime}$, completing the reconstruction.

Case 3: $j=(r+1)/2$. Here the primary vertex $z$ of $C_{1}$ is the central
vertex of $P^{\prime}$. The csc $C_{2}$ shows us all of $T$ except the
offshoots at $z$; in particular, we know $T_{1}$ and $T_{2}$. The Claim
applies to complete the reconstruction of $T$. $\Box$

######  Lemma 3.3.

If $n\geq 6\ell+6$ and $r\geq n-3\ell$, and $T$ contains both $S^{\ell+1}$ and
a sparse card, then $T$ is $\ell$-reconstructible.

###### Proof.

The hypotheses of this lemma are the same as in Lemma 3.2, except for dropping
the restriction that $T$ has only one spi-center. Hence all steps of Lemma 3.2
until we first use the restriction on spi-centers remain valid. In particular,
we have the sparse card $C_{1}$ containing $r$-vertex path $P$ with primary
branch vertex $z$, recognize $k\geq\ell+1$, and see $S^{\ell+1}$ in $T$.
Again, $z$ is a spi-center, and any other spi-center is in $V(C_{1})-V(P)$.
Again, we define $j$ with $j\leq(r+1)/2$ by $z=v_{j}$ with $P$ indexed as
$v_{1},\ldots,v_{r}$. By Lemma 2.18, all $r$-vertex paths have the same
central vertices $v_{j},\ldots,v_{r+1-j}$.

Lemma 3.2 handles the case when $T$ has only one spi-center. Since by
Corollary 2.15 we know the number of spi-centers, we recognize that we are not
in that case. Hence we may assume that $C_{1}$ has at least one vertex in an
offshoot from $P$ at $z$ that is a spi-center. Let $x$ be one such vertex.
Because $P$ is a longest path and some path from $z$ extends along a leg of
$S^{\ell+1}$ beyond $x$, we have $j-1\geq\ell+2$.

Step 1: $z$ and $x$ are the only spi-centers, and we know the distance between
them. Consider the process where we begin with $P$ and iteratively complete a
copy of $S^{\ell+1}$ at a new spi-center of $T$. Each time we do this, we
raise the degree of the new spi-center $v$ from $2$ to $3$ and hence must add
$\ell+1$ vertices in a path emanating from $v$. Hence if $T$ has $s$ spi-
centers, then $T$ has at least $r+s(\ell+1)$ vertices. With $r\geq n-3\ell$,
we thus have $n\geq n-(3-s)\ell+s$, so $s\leq 2$.

Now consider this computation more closely. Let $p$ be the length of the path
from $z$ to $x$. When adding $\ell+1$ vertices off $P$ for the copy of
$S^{\ell+1}$ centered at $z$, we may treat them as beyond $x$, after the $p$
vertices in $T$ on the path from $z$ to $x$. Thus the union of $P$ and two
copies of $S^{\ell+1}$ centered at $z$ and $x$ has $n-\ell+2+p$ vertices. We
conclude $p\leq\ell-2$.

The union $X$ of copies of $S^{\ell+1}$ at $z$ and $x$ consists of four legs
of length $\ell+1$ plus $p+1$ vertices in the path joining $z$ and $x$. Since
$p\leq\ell-2$, we have $\left|V(X)\right|\leq 5\ell+3$. Since $n\geq 6\ell+3$,
we see $X$ in a card, and thus we know $p$.

Step 2: Reconstructing $T_{2}$ and the component of $T-z$ containing $x$,
which we call $Q$. Let $C^{\prime}$ be a largest subtree of $T$ containing
$S_{\ell+1,\ell+1,p+r-j}$ with branch vertex $x^{\prime}$ such that the vertex
$z^{\prime}$ at distance $p$ from $x^{\prime}$ along the long branch of the
spider has degree $2$ in $C^{\prime}$. There is such a subtree with
$x^{\prime}=x$ and $z^{\prime}=z$. Indeed, since $x^{\prime}$ is a spi-center,
we must have $x^{\prime}\in\\{x,z\\}$; since no path of length more than $r-j$
starts from $z$, we have $x^{\prime}=x$. Furthermore, a path of length $p+r-j$
from $x$ must pass through $z$ to avoid having a path longer than $P$, so
$z^{\prime}=z$.

Since $z$ has degree $2$ in $C^{\prime}$, at least $j-1$ vertices of $P$ are
missing from $C^{\prime}$. Since $j-1\geq\ell+2$, we know that $C^{\prime}$
fits in a card. The components of $C^{\prime}-z$ are $T_{2}$ and the offshoot
from $z$ that contains $x$, which we call $Q$. We have not yet determined
other offshoots from $z$, such as those contributing to the sparse card
$C_{1}$ if $z$ has degree more than $3$ in $C_{1}$, but we now know $T_{2}$
and $Q$.

Note that if $j=(r+1)/2$, then in $C^{\prime}$ we see the larger of $T_{1}$
and $T_{2}$, which we call $T_{2}$, but if they have the same size then there
are two choices for $C^{\prime}$ and we obtain both. There cannot be another
offshoot of length $(r-1)/2$ from $z$ besides $T_{1}$, $T_{2}$, and $Q$,
because $r\geq n-3\ell$ implies $3(r-1)/2+2\ell+4>n$.

Step 3: Reconstructing the components of $T-z$ other than $T_{2}$ and $Q$.
Note that $Q$ has at least $2\ell+3$ vertices. Since $r\geq n-3\ell$, any
offshoot from $P$ other than $Q$ has fewer than $\ell$ vertices and hence also
length less than $j-1$. Let $C^{\prime\prime}$ be a largest long subtree
containing $S_{\ell+1,j-1,r-j}$ that has no offshoots from the legs of leg
$\ell+1$ and $j-1$. In such a subtree, the branch vertex of the given spider
must be $z$, and more than $\ell$ vertices are missing from $Q\cup T_{1}$.
Hence $C^{\prime\prime}$ shows us all of $T$ outside $Q\cup T_{1}$.

Since we also know $Q$, it remains only to determine $T_{1}$. If $Q$ has
length less than $j-1$, then every $r$-path lies in $T_{1}\cup T_{2}$. Enlarge
$C^{\prime\prime}$ to a largest subtree containing $S_{\ell+1,j-1,r-j}$ that
has no offshoot from the leg of length $\ell+1$. The leg of length $j-1$ must
lie in $T_{1}$. Again more than $\ell$ vertices are missing from $Q$ and the
subtree fits in a card, showing us $T_{1}$ (if $j-1=r-j$, then we already knew
$T_{1}$).

The remaining case is that $Q$ has length $j-1$, making it unclear whether the
leg of length $j-1$ in the spider in $C^{\prime\prime}$ lies in $Q$ or in
$T_{1}$. Nevertheless, $C^{\prime\prime}$ shows us all components of $T-z$
other than $Q$ and $T_{1}$, and we already know $Q$ from $C^{\prime}$. Hence
we know $\left|V(T_{1})\right|$. We also know the number of $r$-paths, so
knowing $Q$ and $T_{2}$ we can compute the number of peripheral vertices in
$T_{1}$.

Now let ${\mathcal{C}}$ be the family of subtrees containing a vertex
$z^{\prime}$ of degree $2$, such that emerging from $z^{\prime}$ are one path
of length $r-j$ and one offshoot $Y$ of length $j-1$ that need not be a path.
Note that $z^{\prime}$ may be $z$ or $v_{r+1-j}$. Since we know $Q$, $T_{2}$,
and the numbers of peripheral vertices in $Q$, $T_{2}$, and $T_{1}$, we know
all the members of ${\mathcal{C}}$ in which $Y$ comes from $Q$ or $T_{2}$.
After excluding all of these members of ${\mathcal{C}}$, a largest remaining
member of ${\mathcal{C}}$ shows us $T_{1}$. $\Box$

######  Lemma 3.4.

If $n>6\ell+6$ and $r\geq n-3\ell$, and $T$ contains $S^{\ell+1}$ but no
sparse card, then $T$ is $\ell$-reconstructible.

###### Proof.

By Lemma 2.13, we know $r$ from the deck. As noted in Lemma 2.12, $r\geq
3\ell+6$ yields $k\geq\ell+1$. By Corollary 2.15, we then know the number of
spi-centers in $T$, so we know $S^{\ell+1}\subseteq T$ (and hence $r<n-\ell$)
and recognize from the deck that $T$ has no sparse card.

If some spi-center is outside an $r$-path, then it forces at least $2\ell+3$
vertices in one offshoot from the $r$-path, yielding a sparse card when $r\geq
n-3\ell$. With sparse cards forbidden and $S^{\ell+1}$ present, we have a spi-
center on an $r$-path. Among subtrees having an $r$-path $P$ with a spi-center
closest to the center and no other branch vertex on $P$, choose $C_{1}$ to be
one having a longest offshoot from $P$ and, subject to this, having the most
vertices. Let $z$ be the spi-center in $C_{1}$. There may be more than one
largest such card; fix one such as $C_{1}$.

With $V(P)$ indexed as $v_{1},\ldots,v_{r}$, define $j$ with $j\leq(r+1)/2$ by
$z\in\\{v_{j},v_{r+1-j}\\}$. We have chosen $C_{1}$ so that
$\\{v_{j+1},\ldots,v_{r-j}\\}$ contains no spi-center, so all $r$-vertex paths
contain $v_{j},\ldots,v_{r+1-j}$, by Lemma 2.18. Since $T$ has no sparse card,
$C_{1}$ has fewer than $n-\ell$ vertices, and in $C_{1}$ we see all offshoots
from $P$ at $z$ in $T$. Since $C_{1}$ has fewer than $n-\ell$ vertices and
$r\geq n-3\ell$, there is exactly one offshoot $Q$ from $P$ at $z$ that has
length at least $\ell+1$. Also let $T_{1}$ and $T_{2}$ be the components of
$T-z$ containing $v_{j-1}$ and $v_{j+1}$, respectively. In $C_{1}$ we see in
full all offshoots from $z$ in $T$ other than $T_{1}$ and $T_{2}$; from
$T_{1}$ and $T_{2}$ we see only what is in the $r$-path $P$.

Let $C_{2}$ be a largest subtree containing an $r$-path $P^{\prime}$ with
vertices $u_{1},\ldots,u_{r}$ on which the vertices $u_{j}$ and $u_{r+1-j}$
have degree $2$. We have noted that all $r$-paths have the same $r-2j+1$
central vertices. Thus $u_{j}\in\\{v_{j},v_{r+1-j}\\}$. Since $z$ is a spi-
center and has degree $2$ in $C_{2}$, the omitted offshoots at $z$ contain at
least $\ell+1$ vertices. Thus $C_{2}$ fits in a card, and we see $C_{2}$ as a
largest such csc. Since we see also the offshoots from $P^{\prime}$, in
$C_{2}$ we may assume $P^{\prime}=P$, and in $C_{2}$ we see all offshoots from
$P$ except at $v_{j}$ and $v_{r+1-j}$.

Case 1: The length of $Q$ is less than $j-1$. If $j=(r+1)/2$, then $C_{1}$
tells us the offshoots from $C_{2}$ at $v_{j}$, and we have reconstructed $T$.
Hence we may assume $j<(r+1)/2$. We know the offshoots from $P$ at $z$, but we
do not yet know whether $z$ is $v_{j}$ or $v_{r+1-j}$. Let $y$ be the vertex
of $\\{v_{j},v_{r+1-j}\\}$ other than $z$.

Let $W_{1}$ be the union of the offshoots from $P$ at $z$, let $W_{2}$ be the
union of the offshoots at $y$, and let $m_{i}=\left|V(W_{i})\right|$. We
already know $W_{1}$ and $m_{1}$. We also know $m_{2}$, since we know $r$ and
all offshoots from $P$ outside $W_{2}$. We want to find $W_{2}$ and decide
which of $\\{W_{1},W_{2}\\}$ is attached to $v_{j}$.

Suppose first that $m_{2}\geq m_{1}$. Note that $y$ may or may not be a spi-
center. Let $C_{3}$ be a largest subtree containing an $r$-vertex path on
which one of the vertices in positions $j$ and $r+1-j$ has degree $2$. Since
$C_{3}$ omits $m_{1}$ vertices, $C_{3}$ has fewer than $n-\ell$ vertices, and
we see $C_{3}$ in a card as a largest such csc. If $m_{2}>m_{1}$, then we see
$W_{2}$ in position along $P$, together with all offshoots from $P$ except
those in $W_{1}$. We attach $W_{1}$ to the vertex in $\\{v_{j},v_{r+1-j}\\}$
having degree $2$ in $C_{3}$ to complete the reconstruction of $T$.

If $m_{2}=m_{1}$, then there are two choices for $C_{3}$, one showing $W_{2}$
and the other showing $W_{1}$, each occurring in the right position among the
offshoots from $P$. We may have $W_{1}=W_{2}$, and even the two choices for
$C_{3}$ may be the same, but in all cases we complete the reconstruction.

Now suppose $m_{2}<m_{1}$. In this case let $C_{3}$ be a largest subtree
containing an $r$-vertex path $u_{1},\ldots,u_{r}$ such that $u_{j}$ or
$u_{r+1-j}$ has degree $2$, and such that offshoots with a total of $m_{2}+1$
vertices are grown from the other of $\\{u_{j},u_{r+1-j}\\}$. Since $W_{1}\cup
W_{2}$ has $m_{1}+m_{2}$ vertices, $C_{3}$ omits $m_{1}-1$ vertices from
$W_{1}\cup W_{2}$. Since $m_{1}\geq\ell+1$, $C_{3}$ fits in a card, and we see
it as a largest such csc. Since $W_{2}$ has only $m_{2}$ vertices, $C_{3}$
determines which of $\\{v_{j},v_{r+1-j}\\}$ is $z$.

We now know all of $T$ except the offshoots from $P$ at $y$. Let
${\mathcal{C}}_{4}$ be the family of largest subtrees containing an $r$-vertex
path $\langle u_{1},\ldots,u_{r}\rangle$ such that one of $u_{j}$ and
$u_{r+1-j}$ has degree $2$ and the other has offshoots from the path with a
total of $m_{2}$ vertices. Such subtrees omit $m_{1}$ vertices and hence are
visible as cscs. They may arise from $T$ by deleting $m_{1}-m_{2}$ vertices
from $W_{1}$ and all of $W_{2}$, or by deleting all of $W_{1}$. Since we know
$W_{1}$ and where in $C_{2}$ it is attached, we know all the members of
${\mathcal{C}}_{4}$ that arise in the first way. The remaining member of
${\mathcal{C}}_{4}$ shows us $W_{2}$, completing the reconstruction of $T$.

Case 2: $Q$ has length $j-1$. In $C_{1}$ we see $Q$. Since $Q$ has length
$j-1$ and $C_{1}$ was chosen to make $Q$ largest among such offshoots, there
is a choice for $C_{2}$ such that $Q$ is a component of
$C_{2}-\\{v_{j},v_{r+1-j}$ containing an endpoint of $P$. Possibly we can
choose $C_{2}$ so that both such components are $Q$. We choose $C_{2}$ to
maximize the number of such occurrences of $Q$.

Let $W_{1}$ be the union of the offshoots in $T$ from $C_{2}$ at $z$; we do
not yet know $W_{1}$. Since $T$ has no sparse card, $W_{1}$ contains exactly
one offshoot from $C_{2}$ with length at least $\ell+1$; call it $Q^{\prime}$.
Since $C_{1}$ had only $Q$, $T_{1}$, and $T_{2}$ as offshoots from $z$ with
length at least $\ell+1$, the choice of $C_{2}$ in fact implies
$Q^{\prime}=T_{1}$. Let $W_{2}$ be the union of the offshoots from $C_{2}$ at
the vertex in $\\{v_{j},v_{r+1-j}\\}$ other than $z$, and let
$m_{i}=\left|V(W_{i})\right|$.

Since $z$ is a spi-center, $m_{1}\geq m^{\prime}\geq\ell+1$. We may assume
that the path is indexed so that $z=v_{j}$ if $C_{2}$ is symmetric or if
$C_{2}$ is not symmetric and shows only one copy of $Q$ giving a candidate for
$z$.

Subcase 2a: $C_{2}$ is not symmetric (under reversal of $v_{1},\ldots,v_{r}$).
In $C_{2}$ we see at least one copy of $Q$, rooted at $v_{j}$ or $v_{r+1-j}$.
Let $C_{3}$ be a largest csc containing $C_{2}$ in which a root of $Q$ has
degree $2$. Since $C_{2}$ is not symmetric, the vertices $v_{j}$ and
$v_{r+1-j}$ are distinguished by what we see along $C_{2}$, whether or not
they are both roots of copies of $Q$. Hence in addition to $C_{3}$ we can
obtain a largest csc $C^{\prime}_{3}$ containing $C_{2}$ where the added
vertices are in offshoots grown from the other of these two vertices. Since
$m_{1}\geq\ell+1$, there are fewer than $n-\ell$ vertices in $C_{3}^{\prime}$,
so it gives us $W_{2}$ in full. If also $C_{3}$ has fewer than $n-\ell$
vertices, then we obtain both $W_{1}$ and $W_{2}$ with their roots along
$C_{2}$. This completes the reconstruction, since $C_{2}$ shows us the rest of
$T_{2}$ by showing the offshoots at the vertices other than $v_{r+1-j}$.

Hence we may assume that $C_{3}$ is a card, which requires $m_{2}\leq\ell$,
and we know $W_{2}$. We may assume the indexing so that $z=v_{j}$. From what
we see of $T_{2}$ in $C$, plus $W_{2}$, we know $T_{2}$. Subtracting
$\left|V(T_{2})\right|$ and $\left|V(Q)\right|$ from $n-1$ tells us $m_{1}$.
Subtracting the sizes of the small offshoots at $z$ (in $C_{1}$) from $m_{1}$
now gives us $m^{\prime}$, which is $\left|V(T_{1})\right|$.

To find $T_{1}$, let ${\mathcal{C}}_{4}$ be the family of subtrees consisting
of an $r$-vertex path plus one offshoot of length $j-1$ from the $j$th vertex,
such that the offshoot has $m^{\prime}$ vertices. Since
$m^{\prime}\leq\left|V(Q)\right|$, some of these arise by deleting vertices
from $Q$; others show $Q^{\prime}$. Since we know $Q$, we know the number of
ways to find in $Q$ an offshoot of length $j-1$ with $m^{\prime}$ vertices. If
we can determine the number of vertices of $Q^{\prime}$ at distance $j-1$ from
$z$ and the number of vertices at distance $r-j$ from $z$ (we see the latter
in $C_{3}$), then we know all the members of ${\mathcal{C}}_{4}$ to delete. In
the remaining members we see $T_{1}$, completing the reconstruction of $T$.

Consider the subtree $C_{5}$ consisting of an $r$-vertex path
$u_{1},\ldots,u_{r}$ plus one offshoot isomorphic to $Q$ at $u_{j}$. Since $T$
has no sparse card, $C_{5}$ has fewer than $n-\ell$ vertices, and we can count
its appearances in $T$. By the asymmetry of $C_{2}$, we have $u_{j}=z$. Since
we know $W_{2}$, we know how many vertices can serve as $u_{r}$. If
$Q^{\prime}\neq Q$, then the number of vertices that can serve as $u_{1}$ is
the number of vertices of $Q^{\prime}$ at distance $j-1$ from $z$. We can thus
determine this quantity from the number of copies of $C_{5}$.

If $Q^{\prime}=Q$, then we had more than one choice for our original subtree
$C_{1}$, and they were identical, so we knew $Q^{\prime}$ all along.

Subcase 2b: $C_{2}$ is symmetric (under reversal of $v_{1},\ldots,v_{r}$). In
this case, we cannot distinguish $v_{j}$ and $v_{r+1-j}$ in $C_{2}$. We still
consider the family ${\mathcal{C}}_{3}$ of subtrees containing $C_{2}$ in
which $v_{j}$ or $v_{r+1-j}$ has degree $2$. If no csc in ${\mathcal{C}}_{3}$
is a card, then let $C_{3}$ be a largest such csc among those having an
offshoot of length $j-1$ from $C_{2}$. We may assume that the offshoot is at
$v_{j}$, showing us $W_{1}$. Since $W_{1}$ tells us $m_{1}$ and we know
$C_{2}$, we now also know $m_{2}$. If $m_{2}>m_{1}$, then a largest member of
${\mathcal{C}}_{3}$ shows us $W_{2}$. If $m_{2}\leq m_{1}$, then we know all
the members of ${\mathcal{C}}_{3}$ having $m_{2}$ vertices outside $C_{2}$
that arise by deleting $m_{1}-m_{2}$ vertices from $W_{1}$ in $C_{3}$. The
remaining member of ${\mathcal{C}}_{3}$ with $m_{2}$ vertices outside $C_{2}$
shows us $W_{2}$.

Hence we may assume that ${\mathcal{C}}_{3}$ contains a card, so
$m_{2}\leq\ell$. Since $W_{1}$ has at least $\ell+1$ vertices, the offshoots
from $C_{2}$ in cscs that are cards in ${\mathcal{C}}_{3}$ are attached at
$v_{j}$.

We first consider the case $j<(r+1)/2$, postponing $j=(r+1)/2$. Let the
components of $T-z$ containing $v_{j-1}$ and $v_{j+1}$ be $T_{1}$ and $T_{2}$,
respectively. Since $z$ lies in all longest paths as the $j$th vertex from one
end, and $m_{2}\leq\ell$, each copy of $S_{j-1,\ell+1,r-j}$ in $T$ has branch
vertex $z$ and one leaf in each of $Q$, $T_{1}$, and $T_{2}$. Since $z$ is a
spi-center, $\ell+1\leq j-1$, so the same conclusion holds for
$S_{j-1,j-1,r-j}$.

Thus the number of copies of $S_{j-1,j-1,r-j}$ in $T$ is $t_{Q}t_{1}t_{2}$,
where these factors are the numbers of vertices at distance $j-1$ from $z$ in
$Q$, at distance $j-1$ from $z$ in $T_{1}$, and at distance $r-j$ from $z$ in
$T_{2}$, respectively. Since $T$ has no sparse cards, these spiders fit into
cards, so we know the number of them. Knowing $Q$ from $C_{1}$, we know
$t_{Q}$. Since $C_{2}$ is symmetric and $m_{2}\leq\ell$, we have
$t_{2}=t_{Q}$. Hence we can compute $t_{1}$.

As noted, the same properties hold for the smaller spider
$S_{j-1,\ell+1,r-j}$. Again we can count them in the deck, and the number of
them is computed as $t_{Q}s_{1}t_{2}+s_{Q}t_{1}t_{2}$, where $s_{Q}$ and
$s_{1}$ are the numbers of vertices at distance $\ell+1$ from $z$ in $Q$ and
in $T_{1}$, respectively. Since we know $Q$, we know all these numbers except
$s_{1}$, so now we also know $s_{1}$.

Now let ${\mathcal{C}}$ be the family of cscs containing $S_{j-1,\ell+1,r-j}$
such that the leg of length $r-j$ and at least one leg of length $\ell+1$ have
no offshoots ($j-1=\ell+1$ is possible). Again, the branch vertex of the
spider must be $z$. Largest cscs in ${\mathcal{C}}$ may or may not be cards,
but in either case we know all members of ${\mathcal{C}}$ that arise by
choosing the leg of length $\ell+1$ without offshoots from $T_{1}$ and the leg
of length $j-1$ with offshoots from $Q$, since we know $s_{1}$ and $Q$. A
largest csc among the remaining members of ${\mathcal{C}}$ contains a leg of
length $\ell+1$ from $Q$ and shows all of $T_{1}$.

Now we know all of $T$ except $W_{2}$, so we know $m_{2}$. We return to the
family ${\mathcal{C}}_{3}$. Since we know $T_{1}$, we know which members of
${\mathcal{C}}_{3}$ among those having $m_{2}$ vertices in addition to $C_{2}$
are obtained from $C_{2}$ by adding $m_{2}$ vertices from $T_{1}$. After
eliminating them, a remaining member of ${\mathcal{C}}_{3}$ shows us $W_{2}$.

Finally, we have the case $j=(r+1)/2$ with ${\mathcal{C}}_{3}$ containing a
card. There are three offshoots from $z$ with length $j-1$: two copies of $Q$
and one of $T_{1}$, and we know $Q$ and the shorter offshoots. The copies of
$S^{j-1}$ have branch vertex at $z$ and leaves in $T_{1}$ and the two copies
of $Q$. We count them and know $t_{Q}$, so we obtain $t_{1}$ (as defined
above). We can make use of copies of $S_{j-1,\ell+1,r-j}$ and cscs containing
them as above to obtain $T_{1}$. $\Box$

Lemmas 3.2–3.4 cover all cases with $n\geq 6\ell+6$ and $r\geq n-3\ell$ in
which $S^{\ell+1}\subseteq T$, so we have proved that such trees are
$\ell$-reconstructible

##  4 The Vines at the Ends of $P$

In the previous section we proved the $\ell$-reconstructibility of $n$-vertex
trees $T$ with $n\geq 6\ell+6$ under the conditions $r\geq n-3\ell$ and
$S^{\ell+1}\subseteq T$. We next consider trees not containing $S^{\ell+1}$.
Thus forbidding $S^{\ell+1}$ will also forbid $S^{k-1}$ when $k\geq\ell+2$. We
obtain $k\geq\ell+2$ using the computation in Lemma 2.12 and the fact that $k$
is an integer as soon as $r\geq 3\ell+7$, so here we raise the threshold for
$n$ to $n\geq 6\ell+7$.

######  Lemma 4.1.

When $S^{k-1}\not\subseteq T$, in every reconstruction $T$ all longest paths
have the same $r-2k+2$ central vertices, which are all the $(k-1)$-centers in
$T$. The central $r-2k$ vertices are all the $k$-centers in $T$. Thus the two
vertices at distance $k-1$ from the ends of every longest path are
$(k-1)$-centers but not $k$-centers. From the deck, we can determine the two
maximal $(k-1)$-vines $U_{1}$ and $U_{2}$ centered at these two vertices.

###### Proof.

A $(j-1)$-center $v$ outside the central $r-2j+2$ vertices of a longest path
$P$ yields either a longer path than $P$ (if $v\in V(P)$) or a copy of $S^{j}$
(if $v\notin V(P)$). Hence $S^{j}\not\subseteq T$ implies that $T$ has no
$(j-1)$-center outside the central $r-2j+2$ vertices of any longest path.
Those central vertices are indeed $(j-1)$-centers, so all longest paths have
the same central $r-2j+2$ vertices.

Considering $j=k$ and $j=k-1$, we find that the $k$-centers are precisely the
vertices of $P$ except for the last $k$ vertices on each end, and the
$(k-1)$-centers are the vertices of $P$ except for the last $k-1$ vertices on
each end. In particular, the vertices at distance $k-1$ from the ends of $P$
are $(k-1)$-centers but not $k$-centers.

By Corollary 2.9, we know all the maximal $k$-vines and all the maximal
$(k-1)$-vines. Each maximal $k$-vine has a unique center and contains exactly
one maximal $(k-1)$-vine having the same center. Hence we can eliminate the
maximal $(k-1)$-vines contained in $k$-vines from the list of all maximal
$(k-1)$-vines to leave only the two maximal $(k-1)$-vines whose centers have
distance $k-1$ from the ends of $P$. These two $(k-1)$-vines $U_{1}$ and
$U_{2}$ contain the opposite ends of $P$. $\Box$

Reconstructing $T$ requires assembling $U_{1}$ and $U_{2}$ and any part of $T$
omitted by them. Let $x_{i}$ be the center of $U_{i}$. Since
$S^{k-1}\not\subseteq T$, exactly two edges incident to $x_{i}$ in $U_{i}$
start paths of length $k-1$ in $U_{i}$. Our next task is to determine which of
these two edges incident to $x_{i}$ in $U_{i}$ starts the path to $x_{3-i}$.
By “orienting” $U_{i}$, we mean determining which of these two edges in
$U_{i}$ lies along the $x_{1},x_{2}$-path in $P$ (here $P$ is any longest
path). To facilitate this task we introduce definitions and notation for
various objects in the tree.

######  Definition 4.2.

Structure of $U_{i}$. See Figure 2. The edge of $U_{i}$ incident to $x_{i}$
that belongs to the $x_{1},x_{2}$-path in $P$ is the trunk edge of $U_{i}$.
The trunk edge of $U_{i}$ is the central edge in a maximal $(k-1)$-evine. The
other edge of $P$ incident to $x_{i}$ in $U_{i}$ is not the central edge of a
$(k-1)$-evine in $T$.

As noted above, $S^{k-1}\not\subseteq T$ implies that exactly two components
of $U_{i}-x_{i}$ contain $(k-1)$-vertex paths beginning at the neighbor of
$x_{i}$. Let $A_{i}$ and $B_{i}$ respectively be the subtrees of $U_{i}$
rooted at $x_{i}$ that are obtained by deleting the vertex sets of those two
components. Both $A_{i}$ and $B_{i}$ contain all components of $U_{i}-x_{i}$
having no $(k-1)$-vertex path beginning at the neighbor of $x_{i}$. Together
with $x_{i}$, these comprise $A_{i}\cap B_{i}$, and we call this rooted
subtree $W_{i}$.

Figure 2: $U_{i}$

######  Definition 4.3.

$(k-1)$-evines containing $U_{1}$ and $U_{2}$. By Corollary 2.9, we can
determine the number of maximal $(k-1)$-evines and maximal $k$-evines in $T$
with each isomorphism type, and each maximal $k$-evine contains exactly one
maximal $(k-1)$-evine with the same central edge. Therefore, just as we
determined $U_{1}$ and $U_{2}$ in Lemma 4.1, we can also determine the maximal
$(k-1)$-evines $S_{1}$ and $S_{2}$ whose central edges are the trunk edges in
$U_{1}$ and $U_{2}$. From the list of maximal $k$-evines, we obtain a list of
$(k-1)$-evines by deleting the vertices at distance $k$ from the central edge.
The members of the list of maximal $(k-1)$-evines that are not generated in
this process (paying attention to multiplicity) are $S_{1}$ and $S_{2}$.
However, we do not yet know which of $\\{S_{1},S_{2}\\}$ contains which of
$\\{U_{1},U_{2}\\}$.

For $j\in\\{1,2\\}$, let $y_{j}z_{j}$ be the central edge of $S_{j}$. Let
$C_{j}$ and $D_{j}$ be the components of $S_{j}-y_{j}z_{j}$, rooted at $y_{j}$
and $z_{j}$, respectively. Since $S^{k-1}\not\subseteq T$, exactly two
components of $S_{j}-\\{y_{j},z_{j}\\}$ contain paths with $k-1$ vertices
starting from the neighbor of $\\{y_{j},z_{j}\\}$. One is in $C_{j}$ and one
in $D_{j}$; these are the major pieces of $C_{j}$ and $D_{j}$; see Figure 3.

Figure 3: Rooted trees in $S_{j}$

The $(k-1)$-evine $S_{j}$ contains two maximal $(k-1)$-vines, centered at
$y_{j}$ and $z_{j}$. Let $Y_{j}$ be the tree rooted at $y_{j}$ obtained by
deleting the major piece of $C_{j}$ from the maximal $(k-1)$-vine centered at
$y_{j}$. Let $Z_{j}$ be the tree rooted at $z_{j}$ obtained by deleting the
major piece of $D_{j}$ from the maximal $(k-1)$-vine centered at $z_{j}$. Thus
the two maximal $(k-1)$-vines contained in $S_{j}$ are $C_{j}\cup Y_{j}$
(centered at $y_{j}$) and $D_{j}\cup Z_{j}$ (centered at $z_{j}$). Offshoots
from $P$ at $y_{j}$ having length less than $k-1$ lie in both $C_{j}$ and
$Y_{j}$, and similarly for $z_{j}$ and $D_{j}\cap Z_{j}$.

The leaves at maximum distance from the root in a rooted subtree $R$ are the
$R$-extremal vertices or simply the extremal vertices when the rooted subtree
is clear from context. We use this language particularly with these rooted
subtrees where the maximum distance from the root is $k-1$. For example, we
can observe that $C_{j}\cup Y_{j}$ contains all of $S_{j}$ except the extremal
vertices of $D_{j}$, and $D_{j}\cup Z_{j}$ contains all of $S_{j}$ except the
extremal vertices of $C_{j}$.

We may speak of two rooted subtrees of $T$ (such as among those we have
defined above) as being “the same”; this means that those rooted trees are
isomorphic. In particular, we next develop a tool that obtains some
isomorphisms from others.

In Lemma 4.4, $S_{j}$ denotes any $(k-1)$-evine (not necessarily in $T$) whose
branches are $C_{j}$ and $D_{j}$ as in Definition 4.3, with subtrees $Y_{j}$
and $Z_{j}$ also as in Definition 4.3. In one of the applications of Lemma 4.4
where we consider the $(k-1)$-evines containing $U_{1}$ and $U_{2}$ in $T$,
the subtrees in the lemma will indeed be the subtrees of $T$ having these
names in Definition 4.3.

######  Lemma 4.4.

Let $S_{1}$ and $S_{2}$ be $(k-1)$-evines not containing $S^{k-1}$, with
rooted subtrees $(C_{1},Z_{1},Y_{1},D_{1})$ and $(C_{2},Z_{2},Y_{2},D_{2})$ as
in Definition 4.3. If $C_{1}\cong Y_{2}$, $Z_{1}\cong D_{2}$, $Y_{1}\cong
C_{2}$, and $D_{1}\cong Z_{2}$, then $C_{1}\cong Y_{1}$ and $D_{1}\cong
Z_{1}$.

###### Proof.

As in Definition 4.3, let the roots of $C_{1},D_{1},C_{2},D_{2}$ be
$y_{1},z_{1},y_{2},z_{2}$, respectively. In each of these trees, the extremal
vertices are at distance $k-1$ from the root. The given pairs are isomorphic
as rooted trees, so the isomorphisms match the roots.

Since $S^{k-1}$ does not appear, the common subtree $W_{1}$ in $C_{1}$ and
$Y_{1}$ that is rooted at $y_{1}$ and contains no edge of a fixed longest path
in $S_{1}$ has length less than $k-1$. Since $C_{1}\cong Y_{2}$ and
$Y_{1}\cong C_{2}$, also the common subtree of $C_{2}$ and $Y_{2}$ rooted at
$y_{2}$ is $W_{1}$. The analogous observation holds for $W_{2}$ rooted at both
$z_{1}$ and $z_{2}$. In Figure 4, copies of $W_{1}$ are drawn rounded, while
copies of $W_{2}$ are drawn as triangles. We have discussed the copies of
$W_{1}$ and $W_{2}$ as offshoots from the central vertices; we will be
deriving the copies at the neighboring vertices. To facilitate discussion, we
write $A_{1}$ for the isomorphic subtrees $C_{1}$ and $Y_{2}$, $B_{1}$ for
$C_{2}$ and $Y_{1}$, $A_{2}$ for $D_{2}$ and $Z_{1}$, and $B_{2}$ for $D_{1}$
and $Z_{2}$, as shown in Figure 4.

Figure 4: $(k-1)$-evines in Lemma 4.4

Iteratively, moving away from the roots, we will follow paths in the subtrees
$A_{1},A_{2},B_{1},B_{2}$ so that the offshoots from corresponding vertices in
the paths in $A_{1}$ and $B_{1}$ are isomorphic, and similarly for $A_{2}$ and
$B_{2}$. Since paths from the roots have finite length, this iteration leads
to $A_{1}\cong B_{1}$ and $A_{2}\cong B_{2}$, which yields $C_{1}\cong Y_{1}$
and $D_{1}\cong Z_{1}$.

At the roots of $A_{i}$ and $B_{i}$, we have the common subtree $W_{i}$
containing the offshoots of length less than $k-1$. Consider the subtree
$W_{2}$ rooted at $z_{2}$ in $S_{2}$. Not only is $z_{2}$ the root of $Z_{2}$,
which is a copy of $B_{2}$, but also $z_{2}$ is the child outside $W_{1}$ of
the root $y_{2}$ of $Y_{2}$, which is a copy of $A_{1}$. Thus the copy of
$A_{1}$ that appears as $C_{1}$ in $S_{1}$ must also have a copy of $W_{2}$
rooted at the child of $y_{1}$ not in $W_{1}$. Similarly, consider the copy of
$W_{2}$ rooted at $z_{1}$ in $S_{1}$, appearing in $A_{2}$ and $B_{2}$. Since
$z_{1}$ is the child outside $W_{1}$ of the root $y_{1}$ of the copy of
$B_{1}$ in $S_{1}$, the copy of $B_{1}$ in $S_{2}$ also has $W_{2}$ rooted at
the child of $y_{2}$ not in $W_{1}$. We have thus obtained isomophism between
subtrees at the children of $y_{1}$ in $A_{1}$ and $B_{1}$.

Also, the copy of $A_{1}$ occurring as $Y_{2}$ has only one child of $z_{2}$
outside $W_{2}$. Hence for the copy of $A_{1}$ occurring as $C_{1}$ in
$S_{1}$, also there is only one child outside $W_{2}$ for the vertex whose
offshoots we have found to be $W_{2}$, thereby leaving a unique path to follow
(similarly for $B_{1}$.

Analogous arguments starting from the copies of $W_{1}$ rooted at $y_{2}$ in
$S_{2}$ and at $y_{1}$ in $S_{1}$ give us isomorphism between the subtrees at
the child of the root of $A_{2}$ in $S_{2}$ and at the child of the root of
$B_{2}$ in $S_{1}$.

At the child of the root along the path, we have just found a copy of $W_{2}$
in $A_{1}$ in $S_{1}$, a copy of $W_{1}$ in $B_{2}$ in $S_{1}$, a copy of
$W_{2}$ in $B_{1}$ in $S_{2}$, and a copy of $W_{1}$ in $A_{2}$ in $S_{2}$,
where these hosts are the “outer” subtrees together covering all of $S_{1}$
and $S_{2}$ except the central edges. Since the roots of these new copies of
$W_{1}$ and $W_{2}$ are one step from the centers of $S_{1}$ and $S_{2}$ in
these hosts, the copies of $W_{1}$ and $W_{2}$ may contain vertices that are
extremal in these host subtrees. These extremal vertices are deleted when we
view these offshoots as subtrees of the “inner” subtrees, moving from $A_{1}$
to $A_{2}$ in $S_{1}$, from $B_{2}$ to $B_{1}$ in $S_{1}$, from $B_{1}$ to
$B_{2}$ in $S_{2}$, and from $A_{2}$ to $A_{1}$ in $S_{2}$.

Since these copies of $W_{i}$ are isomorphic and at the same distance from the
center, the truncations obtained by deleting vertices that are extremal in the
inner hosts are also isomorphic. In comparing the inner subtrees after the
truncation ($A_{2}$ in $S_{1}$ with $B_{2}$ in $S_{2}$, and $B_{1}$ in $S_{1}$
with $A_{1}$ in $S_{2}$) we see the isomorphism at the next step moving away
from the root. As we move along, the isomorphic subtrees we extract in $A_{i}$
and $B_{i}$ will be iterated truncations of $W_{1}$ alternating with iterated
truncations of $W_{2}$.

Having obtained isomorphism at a new level using the inner subtrees, we view
them and the unique leftover edge continuing the path as located in the outer
subtrees in the other $(k-1)$-evine. There we must truncate farthest vertices
to obtain the next level in the inner subtrees. At each step, the same
operations are occurring in $A_{i}$ and in $B_{i}$, so we obtain the
isomorphism level by level. $\Box$

In our applications of Lemma 4.4 to $T$, the labels do indicate subtrees as in
Definitions 4.2 and 4.3. Although we know the $(k-1)$-vines $U_{1}$ and
$U_{2}$ that appear in $T$ but are not contained in $k$-vines, and we know the
$(k-1)$-evines $S_{1}$ and $S_{2}$ that contain them, we don’t yet know which
of $S_{1}$ and $S_{2}$ contains which of $U_{1}$ and $U_{2}$. Postponing that
issue, we show next that if we do know that $U_{i}$ appears in $S_{j}$, so
that $y_{j}z_{j}$ is the trunk edge of $U_{i}$ with $x_{i}$ occurring as
$y_{j}$ or $z_{j}$, then we will be able to determine which of $y_{j}$ and
$z_{j}$ is $x_{i}$. This is equivalent to determining which of $C_{j}\cup
Y_{j}$ and $D_{j}\cup Z_{j}$ is that occurrence of $U_{i}$. If $U_{i}$ occurs
as $C_{j}\cup Y_{j}$, then $y_{j}$ is $x_{i}$ and $C_{j}$ is $A_{i}$ or
$B_{i}$. If $U_{i}$ occurs as $D_{j}\cup Z_{j}$, then $z_{j}$ is $x_{i}$ and
$D_{j}$ is $A_{i}$ or $B_{i}$.

When we write that two $4$-tuples of rooted trees are equal, we mean that
corresponding entries are isomorphic. Similarly, writing that a rooted tree is
not in a set of rooted trees means that it is not isomorphic to any of the
members, and the size of a set of rooted trees is the number of isomorphism
classes in it.

######  Lemma 4.5.

Fixing $i,j\in\\{1,2\\}$, if $S_{j}$ is known to be the maximal $(k-1)$-evine
whose central edge is the trunk edge of $U_{i}$, then the edge of $U_{i}$
serving as the trunk edge is recognizable.

###### Proof.

By definition, $x_{i}$ is $y_{j}$ or $z_{j}$. If $x_{i}=y_{j}$, then
$U_{i}=C_{j}\cup Y_{j}$ and the trunk edge of $U_{i}$ is in $B_{i}$. If
$x_{i}=z_{j}$, then $U_{i}=D_{j}\cup Z_{j}$ and the trunk edge of $U_{i}$ is
in $A_{i}$. Hence we want to determine which of $y_{j}$ and $z_{j}$ is
$x_{i}$.

One of $\\{C_{j},D_{j}\\}$ must be $A_{i}$ or $B_{i}$. By symmetry, we may
label the subtrees so that $C_{j}\cong A_{i}$. If $D_{j}\not\cong B_{i}$, then
$y_{j}=x_{i}$. Hence we may assume both $C_{j}\cong A_{i}$ and $D_{j}\cong
B_{i}$.

If $x_{i}=z_{j}$, then $Z_{j}\cong A_{i}$, but if $x_{i}=y_{j}$, then
$Y_{j}\cong B_{i}$. Hence if $Z_{j}\not\cong A_{i}$ or $Y_{j}\not\cong B_{i}$,
then we have located $x_{i}$ in $S_{j}$. Hence we may assume both $Z_{j}\cong
A_{i}$ and $Y_{j}\cong B_{i}$.

We claim that this requires $A_{i}\cong B_{i}$. Instead of building an
isomorphism as in Lemma 4.4, we apply Lemma 4.4 by using another copy of
$S_{j}$. Let $S^{\prime}$ be the $(k-1)$-evine obtained by reversing the
labeling of $S_{j}$, making subtrees
$C^{\prime},Z^{\prime},Y^{\prime},D^{\prime}$ in $S^{\prime}$ isomorphic to
$D_{j},Y_{j},Z_{j},C_{j}$, respectively. Thus
$(C_{j},Z_{j},Y_{j},D_{j})=(A_{i},A_{i},B_{i},B_{i})$ and
$(C^{\prime},Z^{\prime},Y^{\prime},D^{\prime})=(B_{i},B_{i},A_{i},A_{i})$.
With $S_{j}$ playing the role of $S_{1}$ and $S^{\prime}$ playing the role of
$S_{2}$ in Lemma 4.4, we have the isomorphic pairs of subtrees
$(C_{j},Y^{\prime})$, $(Z_{j},D^{\prime})$, $(Y_{j},C^{\prime})$, and
$(D_{j},Z^{\prime})$ needed to apply Lemma 4.4.

We conclude that $C_{j}\cong Y_{j}$ or $D_{j}\cong Z_{j}$: that is,
$A_{i}\cong B_{i}$. Thus in this case $U_{i}$ is symmetric, and we may choose
either edge incident to $x_{i}$ along $P$ as the trunk edge of $U_{i}$. $\Box$

######  Lemma 4.6.

If some member of $\\{C_{1},C_{2},D_{1},D_{2}\\}$ does not belong to
$\\{A_{1},A_{2},B_{1},B_{2}\\}$ (as a rooted tree), then the trunk edges of
$U_{1}$ and $U_{2}$ are recognizable.

###### Proof.

By symmetry, we may assume $C_{1}\notin\\{A_{1},A_{2},B_{1},B_{2}\\}$. Thus
$y_{1}\notin\\{x_{1},x_{2}\\}$, so $z_{1}\in\\{x_{1},x_{2}\\}$. That is,
$D_{1}\cup Z_{1}\in\\{U_{1},U_{2}\\}$, so
$D_{1}\in\\{A_{1},A_{2},B_{1},B_{2}\\}$. The rooted trees
$A_{1},A_{2},B_{1},B_{2}$ need not be distinct; $D_{1}$ may be isomorphic to
more than one of them.

If $D_{1}$ is isomorphic to exactly one of them, which by symmetry we may
assume is $A_{1}$, then $z_{1}=x_{1}$ and we know that the trunk edge in
$U_{1}$ lies in $B_{1}$, not $A_{1}$. Also, since $D_{1}$ is not isomorphic to
$A_{2}$ or $B_{2}$, we have $U_{2}\subseteq S_{2}$, and Lemma 4.5 completes
the proof.

Hence we may assume that $D_{1}$ is isomorphic to more than one of
$\\{A_{1},A_{2},B_{1},B_{2}\\}$. By symmetry, we again assume $D_{1}=A_{1}$.
If $D_{1}$ is not isomorphic to $A_{2}$ or $B_{2}$, then $D_{1}=A_{1}\cong
B_{1}$ and it does not matter which candidate is the trunk edge of $U_{1}$.
Since neither $C_{1}$ nor $D_{1}$ is in $\\{A_{2},B_{2}\\}$, we have
$U_{1}\subseteq S_{1}$ and $U_{2}\subseteq S_{2}$ as actual subgraphs of $T$,
and Lemma 4.5 on $U_{2}$ and $S_{2}$ completes the proof.

In the remaining case, by symmetry, $D_{1}=A_{1}\cong A_{2}$. If also
$B_{1}\cong B_{2}$, then $U_{1}\cong U_{2}$. Now it does not matter which
$U_{i}$ we view as lying in which $S_{j}$ in $T$, so we can assign them
arbitrarily and use Lemma 4.5 to complete the proof.

Hence we may assume $D_{1}=A_{1}\cong A_{2}$ and $B_{1}\not\cong B_{2}$. Again
$z_{1}\in\\{x_{1},x_{2}\\}$, so $D_{1}\cup Z_{1}$ is $U_{1}$ or $U_{2}$. Since
$B_{1}\not\cong B_{2}$, now $Z_{1}$ is isomorphic to just one of $B_{1}$ or
$B_{2}$; let it be $B_{j}$. Now $z_{1}=x_{j}$, the trunk edge of $U_{j}$ is in
$B_{j}$, and $U_{3-j}\subseteq S_{2}$, so Lemma 4.5 completes the proof.
$\Box$

In the remaining cases,
$\\{C_{1},C_{2},D_{1},D_{2}\\}\subseteq\\{A_{1},A_{2},B_{1},B_{2}\\}$. In
light of Lemma 4.5, our goal is to find which of $S_{1}$ and $S_{2}$ contains
which of $U_{1}$ and $U_{2}$. We break this into three lemmas, depending on
how many isomorphism classes of rooted trees comprise
$\\{A_{1},A_{2},B_{1},B_{2}\\}$.

######  Lemma 4.7.

If $\left|\\{A_{1},A_{2},B_{1},B_{2}\\}\right|\leq 2$, then the trunk edges of
$U_{1}$ and $U_{2}$ are recognizable.

###### Proof.

If neither of $\\{A_{1},B_{1}\\}$ is isomorphic to either of
$\\{A_{2},B_{2}\\}$, then having at most two isomorphism classes requires
$A_{1}\cong B_{1}$ and $A_{2}\cong B_{2}$. In this case, $U_{1}$ and $U_{2}$
are symmetric and in each the choice of trunk edges from the two candidates
does not matter. This case includes that of $A_{1}$, $A_{2}$, $B_{1}$, and
$B_{2}$ being pairwise isomorphic.

In the remaining case, a member of $\\{A_{1},B_{1}\\}$ is isomorphic to a
member of $\\{A_{2},B_{2}\\}$. By symmetry in the labeling, we may assume
$A_{1}\cong A_{2}$ and call this rooted tree $A$. If $B_{1}\cong B_{2}$, then
$U_{1}\cong U_{2}$, and we can view $U_{1}$ and $U_{2}$ as contained in
$S_{1}$ and $S_{2}$, respectively, applying Lemma 4.5 to find the trunk edges.

Hence we may assume $B_{1}\not\cong B_{2}$. Since the four subtrees lie in two
isomorphism classes, we may assume by symmetry in the indices that $B_{1}\cong
A_{1}\cong A_{2}\cong A$ and $B_{2}\not\cong A$. Now $U_{1}$ is symmetric and
the choice of its trunk edge does not matter, so it remains to determine the
trunk edge of $U_{2}$. If $B_{2}$ does not occur as any of the branches
$\\{C_{1},C_{2},D_{1},D_{2}\\}$, then $B_{2}$ cannot contain the end of a
longest path and instead contains the trunk edge of $U_{2}$.

Let $B=B_{2}$. In the remaining case, $B\in\\{C_{1},C_{2},D_{1},D_{2}\\}$. We
have made no comment yet distinguishing branches of $S_{1}$ or $S_{2}$, so by
symmetry we may assume $D_{2}\cong B$. Now if $C_{2}\not\cong A$, then neither
branch of $S_{2}$ is $A_{1}$ or $B_{1}$, so $U_{1}\not\subseteq S_{2}$ in $T$.
This forces $U_{2}\subseteq S_{2}$, and we apply Lemma 4.5. Hence we may
assume $C_{2}\cong A$ and $D_{2}\cong B$. If $S_{1}\cong S_{2}$, then we can
apply Lemma 4.5 with $U_{2}\subseteq S_{2}$ or $U_{2}\subseteq S_{1}$. Hence
we may assume $S_{1}\not\cong S_{2}$.

Since $A_{1}\cong B_{1}\cong A\not\cong B\cong D_{2}$, we have $U_{1}\subseteq
S_{2}$ only if $Y_{2}\cong A$. Therefore, if $Y_{2}\not\cong A$, then we know
$U_{1}\not\subseteq S_{2}$, which forces $U_{2}\subseteq S_{2}$, and we apply
Lemma 4.5.

Hence we may assume $Y_{2}\cong A$ and $U_{1}\subseteq S_{2}$. We are confused
about how to apply Lemma 4.5 only if $U_{2}$ occurs in both $S_{1}$ and
$S_{2}$. For $U_{2}\subseteq S_{2}$, we must have $Z_{2}\cong A_{2}\cong A$.
That is, $C_{2}\cong Z_{2}\cong Y_{2}\cong A$ and $D_{2}\cong B$. On the other
hand, confusion also requires having both $U_{1}$ and $U_{2}$ occur in
$S_{1}$. With $S_{1}\not\cong S_{2}$, by symmetry in the labels we may assume
$C_{1}\cong Z_{1}\cong D_{1}\cong A$ and $Y_{1}\cong B$. See Figure 5.

Now we modify Figure 5 by relabeling to reverse $S_{2}$, viewing the subtrees
$(A,A,A,B)$ as $(D_{2},Y_{2},Z_{2},C_{2})$ instead of
$(C_{2},Z_{2},Y_{2},D_{2})$. With this relabeling, since
$(C_{1},Z_{1},Y_{1},D_{1})=(A,A,B,A)$, we have $C_{1}\cong Y_{2}$, $Z_{1}\cong
D_{2}$, $Y_{1}\cong C_{2}$, and $D_{1}\cong Z_{2}$. By Lemma 4.4, we conclude
$C_{1}\cong Y_{1}$ and $D_{1}\cong Z_{1}$. In other words, $A\cong B$, which
is forbidden in this case. $\Box$

Figure 5: $(k-1)$-evines in Lemma 4.7

######  Lemma 4.8.

If $\left|\\{A_{1},A_{2},B_{1},B_{2}\\}\right|=3$, then the trunk edges of
$U_{1}$ and $U_{2}$ are recognizable.

###### Proof.

Again let $W_{1}=A_{1}\cap B_{1}$ and $W_{2}=A_{2}\cap B_{2}$. By hypothesis,
two of $\\{A_{1},A_{2},B_{1},B_{2}\\}$ are isomorphic. By Lemma 4.5, we can
recognize the trunk edges in $U_{1}$ and $U_{2}$ unless each of $U_{1}$ and
$U_{2}$ appears in both $S_{1}$ and $S_{2}$ as a subgraph and $S_{1}\not\cong
S_{2}$.

Case 1: $A_{1}\cong B_{1}$ or $A_{2}\cong B_{2}$, from the same $U_{i}$. By
symmetry, we may assume $A_{1}\cong B_{1}\cong A$, so the choice of trunk edge
for $U_{1}$ does not matter. As noted above, we must have $U_{1}$ in both
$S_{1}$ and $S_{2}$, so we have both $A\in\\{C_{1},D_{1}\\}$ and
$A\in\\{C_{2},D_{2}\\}$. However, since $A$ is neither $A_{2}$ nor $B_{2}$ and
$U_{2}$ must also appear in both $S_{1}$ and $S_{2}$, we may assume by
symmetry in the labeling that $C_{1}=C_{2}=A$ and that neither $D_{1}$ nor
$D_{2}$ is $A$.

Since confusion requires $S_{1}\not\cong S_{2}$, we may assume $D_{1}=A_{2}$
and $D_{2}=B_{2}$, with $U_{2}$ occurring as both $Z_{1}\cup D_{1}$ and
$Z_{2}\cup D_{2}$. In $S_{1}$, deleting the extremal vertices of $A$ (as
$C_{1}$) and adding $W_{2}$ above the root yields $Z_{1}$ and hence $B_{2}$.
In $S_{2}$, deleting the extremal vertices of $A$ (as $C_{2}$) and adding
$W_{2}$ above the root yields $Z_{2}$ and hence $A_{2}$. Thus $A_{2}=B_{2}$,
which contradicts the hypothesis of this case.

Case 2: $A_{1}$ or $B_{1}$ (from $U_{1}$) is isomorphic to $A_{2}$ or $B_{2}$
(from $U_{2}$). By symmetry, we may assume $A_{1}\cong A_{2}\cong A$. Here all
of $\\{A,B_{1},B_{2}\\}$ are different, but $W_{1}\cong W_{2}$ since each is
obtained from $A$ in the same way.

If $A\notin\\{C_{1},C_{2},D_{1},D_{2}\\}$, then the ends of $U_{1}$ and
$U_{2}$ occupied by $A$ do not occur at an end of $S_{1}$ or $S_{2}$, so the
trunk edges in $U_{1}$ and $U_{2}$ both lie in $A$. Hence we may assume
$C_{1}\cong A$. If also $D_{1}\cong A$, then $U_{1}$ and $U_{2}$ both
appearing in $S_{1}$ requires $\\{Y_{1},Z_{1}\\}=\\{B_{1},B_{2}\\}$. Also,
since $C_{1}\cong A\cong D_{1}$, the rooted subtrees at $y_{1}$ and $z_{1}$
outside the major pieces both equal $W_{1}$. Hence both $Y_{1}$ and $Z_{1}$
arise by deleting the extremal vertices of $A$ and adding $W_{1}$ at the top.
This yields $Y_{1}\cong Z_{1}$ and $B_{1}\cong B_{2}$, which contradicts the
hypothesis.

Hence we may assume $D_{1}\not\cong A$. By Lemma 4.6 and symmetry in the
indices, we may now assume $D_{1}\cong B_{2}$. Since $U_{1}$ and $U_{2}$ must
both appear in $S_{1}$, we have $Y_{1}\cong B_{1}$ and $Z_{1}\cong A$; that
is, $U_{1}\cong C_{1}\cup Y_{1}$ and $U_{2}\cong Z_{1}\cup D_{1}$.

Now consider $S_{2}$. By reversing the labeling of $S_{2}$ if needed, we may
assume $U_{1}=C_{2}\cup Y_{2}$ and $U_{2}=Z_{2}\cup D_{2}$. Hence
$C_{2}\in\\{A,B_{1}\\}$ and $D_{2}\in\\{A,B_{2}\\}$. This leaves four cases.

(a) $(C_{2},D_{2})=(A,B_{2})$. Here $S_{2}\cong S_{1}$, so Lemma 4.5 applies
with either assignment.

(b) $(C_{2},D_{2})=(A,A)$. Here the argument in Case 1 about deleting the
extremal vertices from $A$ and adding another copy of the root offshoots above
the root yields $Y_{2}\cong Z_{2}$ and hence $B_{1}\cong B_{2}$, a
contradiction.

(c) $(C_{2},D_{2})=(B_{1},B_{2})$. In $S_{1}$, deleting the extremal vertices
of $B_{2}$ and adding $W_{1}$ above the root yields $B_{1}$. In $S_{2}$,
deleting the extremal vertices of $B_{2}$ and adding $W_{1}$ above the root
yields $A$. Hence $B_{1}\cong A$, a contradiction.

(d) $(C_{2},D_{2})=(B_{1},A)$. Now
$(C_{1},Z_{1},Y_{1},D_{1})=(A,A,B_{1},B_{2})$, and also
$(C_{2},Z_{2},Y_{2},D_{2})=(B_{1},B_{2},A,A)$. In particular, we have
isomorphic pairs $(C_{1},Y_{2})$, $(Z_{1},D_{2})$, $(Y_{1},C_{2})$, and
$(D_{1},Z_{2})$. By Lemma 4.4, $A\in\\{B_{1},B_{2}\\}$, again a contradiction.
$\Box$

######  Lemma 4.9.

If $\left|\\{A_{1},A_{2},B_{1},B_{2}\\}\right|=4$, then the trunk edges of
$U_{1}$ and $U_{2}$ are recognizable.

###### Proof.

Here $A_{1},A_{2},B_{1},B_{2}$ are distinct. Again by Lemma 4.5 we have the
desired result unless $S_{1}\not\cong S_{2}$ and each of $U_{1}$ and $U_{2}$
appears in both $S_{1}$ and $S_{2}$. By Lemma 4.6, we may assume
$\\{C_{1},C_{2},D_{1},D_{2}\\}\subseteq\\{A_{1},A_{2},B_{1},B_{2}\\}$.

Case 1: Some member of $\\{A_{1},A_{2},B_{1},B_{2}\\}$ is not in
$\\{C_{1},C_{2},D_{1},D_{2}\\}$. By symmetry, we may assume
$A_{1}\notin\\{C_{1},C_{2},D_{1},D_{2}\\}$. In order to have $U_{1}$ appear in
both $S_{1}$ and $S_{2}$, we must have $B_{1}$ as an end-subtree in both
$S_{1}$ and $S_{2}$. By symmetry, we may assume $D_{1}\cong D_{2}\cong B_{1}$.
Now, since $U_{2}$ appears in both $S_{1}$ and $S_{2}$ and $S_{1}\not\cong
S_{2}$, we may assume $C_{1}\cong A_{2}$ and $C_{2}\cong B_{2}$. To complete
the copies of $U_{2}$ in $S_{1}$ and $S_{2}$, we must have $Y_{1}\cong B_{2}$
and $Y_{2}\cong A_{2}$.

At this point, the subtree $W_{2}$ that is $A_{2}\cap B_{2}$ rooted at $x_{2}$
appears both in $S_{1}$ rooted at $y_{1}$ and in $S_{2}$ rooted at $y_{2}$.
These are the portions of $Y_{1}$ and $Y_{2}$ that do not lie in $D_{1}$ and
$D_{2}$, respectively. Since $D_{1}\cong D_{2}\cong B_{1}$, deleting the
extremal vertices of $B_{1}$ and placing $W_{2}$ atop the root of $B_{1}$
yields $B_{2}$ by looking at $Y_{1}$ in $S_{1}$ and $A_{2}$ by looking at
$Y_{2}$ in $S_{2}$. Hence $A_{2}\cong B_{2}$, contradicting the hypothesis.

Case 2: All of $\\{A_{1},B_{1},A_{2},B_{2}\\}$ appear in
$\\{C_{1},C_{2},D_{1},D_{2}\\}$, and hence there is a bijection via
isomorphisms from one set of subtrees to the other. Recall that
$U_{i}=A_{i}\cup B_{i}$.

Since each of $U_{1}$ and $U_{2}$ appears in both $S_{1}$ and $S_{2}$, we may
assume by symmetry that $C_{1}\cong A_{1}$, and hence $Y_{1}\cong B_{1}$ with
$W_{1}$ rooted at $y_{1}$. Reversing the labeling of $U_{2}$ if necessary,
this leaves $D_{1}\cong B_{2}$ and $Z_{1}\cong A_{2}$, so
$(C_{1},Z_{1},Y_{1},D_{1})=(A_{1},A_{2},B_{1},B_{2})$. Since $U_{1}$ and
$U_{2}$ must also appear in $S_{2}$, with
$\\{C_{2},D_{2}\\}=\\{A_{2},B_{1}\\}$ by the hypothesis of this case, we may
reverse the labeling of $S_{2}$ if necessary to obtain
$(C_{2},Z_{2},Y_{2},D_{2})=(B_{1},B_{2},A_{1},A_{2})$ (see Figure 4). By Lemma
4.4, we obtain $A_{1}\cong A_{2}$ or $B_{1}\cong B_{2}$, contradicting the
hypothesis. $\Box$

######  Corollary 4.10.

The trunk edges of $U_{1}$ and $U_{2}$ are recognizable.

###### Proof.

With $U_{1},U_{2},S_{1},S_{2}$ and their subtrees $A_{1},B_{1},A_{2},B_{2}$
and $C_{1},D_{1},C_{2},D_{2}$ known from the deck, Lemmas 4.6 through 4.9
treat an exhaustive set of cases where arguments applying Lemmas 4.4 and 4.5
are used to recognize the trunk edges of $U_{1}$ and $U_{2}$, thereby
determining which of $\\{A_{1},B_{1}\\}$ and which of $\\{A_{2},B_{2}\\}$
contain the ends of a longest path $P$ in $T$. $\Box$

##  5 Large Diameter and no Spi-center

In this section we continue and complete the reconstruction of trees having
large diameter and no spi-center (no copy of $S^{\ell+1}$). Henceforth we
assume $n\geq 6\ell+11$. With also $r\geq n-3\ell$, the usual computation from
Lemma 2.12 yields $k\geq\ell+4$. By Lemma 2.15, we can then count the spi-
centers in $T$ and thus recognize $S^{\ell+1}\not\subseteq T$.

######  Definition 5.1.

In the previous section we determined the two maximal $(k-1)$-vines $U_{1}$
and $U_{2}$ whose centers are distance $k-1$ from the endpoints of any longest
path in the $n$-vertex tree $T$ whose $(n-\ell)$-deck we are given. Since
$k-1\geq\ell+1$ and $S^{\ell+1}\not\subseteq T$, in both $U_{1}$ and $U_{2}$
only two pieces have the full length $k-1$ (the “major” pieces). Also, we have
successfully oriented each of these $(k-1)$-vines, meaning that we know which
is the “outer” major piece containing an endpoint of each longest path and
which is the “inner” major piece extending toward the other $(k-1)$-vine.

We maintain the notation $U_{1}$ and $U_{2}$ for those maximal $(k-1)$-vines,
with $x_{i}$ the center of $U_{i}$. Since $S^{\ell+1}\not\subseteq T$ and
$k-1\geq\ell+1$, every $r$-path in $T$ contains the path from $x_{1}$ to
$x_{2}$; we use this implicitly without mention throughout this section. The
distance between $x_{1}$ and $x_{2}$ is $r+1-2k$. Since $k\geq(r-\ell-4)/2$ by
Lemma 2.12, the distance between $x_{1}$ and $x_{2}$ is at most $\ell+5$.

For $i\in\\{1,2\\}$, inner extremal vertices in $U_{i}$ are vertices at
distance $k-1$ from $x_{i}$ in the inner piece. If there are multiple inner
extremal vertices in $U_{i}$, then let $x_{i}^{\prime}$ be the vertex closest
to $x_{i}$ in the inner piece at which paths to inner extremal vertices in
$U_{i}$ diverge. If there is no such vertex, then let $x_{i}^{\prime}$ be the
unique extremal vertex in the inner piece, having distance $k-1$ from $x_{i}$
along $P$.

######  Lemma 5.2.

For $i\in\\{1,2\\}$, all offshoots from $P$ in $T$ at vertices between $x_{i}$
and $x_{i}^{\prime}$ (not including $x_{i}^{\prime}$) are seen in full in
$U_{i}$. Furthermore, $x_{1}^{\prime}$ and $x_{2}^{\prime}$ are strictly
between $x_{1}$ and $x_{2}$ on $P$, and we know their order along $P$.

###### Proof.

All vertices having distance at most $k-1$ from $x_{i}$ are seen in $U_{i}$.
An offshoot at a vertex between $x_{i}$ and $x_{i}^{\prime}$ containing a
vertex with distance at least $k-1$ from $x_{i}$ would contradict the
definition of $x_{i}^{\prime}$.

For each $i$, the vertex $x_{i}^{\prime}$ lies in the inner piece of $U_{i}$.
Since we have determined which is the inner piece, we know $x_{i}^{\prime}$ in
$U_{i}$, and the path from $x_{i}$ to $x_{i}^{\prime}$ lies along $P$ in the
direction toward $x_{3-i}$. We also know the distance from $x_{i}$ to
$x_{i}^{\prime}$, and the distance from $x_{1}$ to $x_{2}$ is $r+1-2k$. Hence
we know the order of $\\{x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2}\\}$ along
$P$ and whether $x_{1}^{\prime}=x_{2}^{\prime}$. $\Box$

We consider cases depending on the order and distinctness of $x_{1}^{\prime}$
and $x_{2}^{\prime}$, which we have just shown are recognizable.

######  Lemma 5.3.

If $x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2}$ occur along $P$ in the order
$(x_{1},x_{2}^{\prime},x_{1}^{\prime},x_{2})$ with $x_{2}^{\prime}\neq
x_{1}^{\prime}$, then $T$ is $\ell$-reconstructible.

###### Proof.

We know the outer pieces of $U_{1}$ and $U_{2}$ and the offshoots at $x_{1}$
and $x_{2}$ with length less than $k-1$. Adding the centers $x_{1}$ and
$x_{2}$ and a path of length $r+1-2k$ joining them yields a subtree of $T$
containing an $r$-path we call $P$. It remains to determine the offshoots from
$P$ along the path joining $x_{1}$ and $x_{2}$. Every offshoot at a vertex
between $x_{i}$ and $x_{i}^{\prime}$ is seen in full in $U_{i}$, by Lemma 5.2.
With the vertices in the specified order, all the needed offshoots are seen in
full. $\Box$

######  Lemma 5.4.

If $x_{1}^{\prime}=x_{2}^{\prime}$, then $T$ is $\ell$-reconstructible.

###### Proof.

By Lemma 5.2, we recognize this case and we know everything in $T$ except the
offshoots from $P$ at the vertex called both $x_{1}^{\prime}$ and
$x_{2}^{\prime}$. Their length is less than $k-1$, since $k-1\geq\ell+1$ and
$S^{\ell+1}\not\subseteq T$. Hence they appear in full in the $k$-vine
centered at $x_{1}^{\prime}$.

We know the maximal $k$-vines in $T$; the $k$-centers are on $P$ between
$x_{1}$ and $x_{2}$. Each has only two offshoots of length $k$ from the
center; we take its rooted subgraph obtained by deleting those two pieces.
Knowing all of $T$ except the offshoots from $x_{1}^{\prime}$, we can exclude
from this list of subgraphs the ones that come from $k$-centers other than
$x_{1}^{\prime}$, with correct multiplicity. What remains is the rooted
subgraph at $x_{1}^{\prime}$, completing the reconstruction of $T$. $\Box$

######  Lemma 5.5.

If $r\geq n-2\ell$ and $n\geq 6\ell+11$ and $x_{1}^{\prime}\neq
x_{2}^{\prime}$, then $x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2}$ must occur
in the order $(x_{1},x_{2}^{\prime},x_{1}^{\prime},x_{2})$ along $P$.

###### Proof.

For each $i$, the path from $x_{i}^{\prime}$ to an extremal vertex in $U_{i}$
outside $P$ has length at most $\ell$, since $S^{\ell+1}\not\subseteq T$.
Extending such a path from the extremal vertex back through $x_{i}$ to the end
of $P$ yields a path with $2k-1$ vertices. The resulting paths for
$i\in\\{1,2\\}$ are disjoint when the vertices are in the order
$x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2}$. Since together these paths have
at most $2\ell$ vertices outside $P$, we have $r\geq 4k-2-2\ell$. Lemma 2.12
then yields $r\geq 2r-2\ell-8-2-2\ell$, which simplifies to $r\leq 4\ell+10$.
With $r\geq n-2\ell\geq 4\ell+11$, we have a contradiction. $\Box$

By Lemmas 5.2–5.5, we may assume in the remainder of this section that
$x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2}$ are distinct and occur in that
order and that $n-3\ell\leq r\leq n-2\ell-1$,

######  Lemma 5.6.

If some longest path has vertices $y$ and $y^{\prime}$ equidistant from the
ends (and distance at least $k$ from the ends) such that the offshoots from
the path at $y$ and $y^{\prime}$ together have more than $\ell$ vertices, then
$T$ is $\ell$-reconstructible.

###### Proof.

First we observe that this case is recognizable. We consider subtrees
containing an $r$-vertex path and offshoots from the path only at two vertices
that are equidistant (with distance at least $k$) from the ends. If in some
such subtree the offshoots have $\ell+1$ vertices in total, then the subtree
fits in a card (since $r\leq n-2\ell-1$), and we see it in a csc.

Since $S^{\ell+1}\not\subseteq T$ and $k-1\geq\ell+1$, every longest path
contains the path from $x_{1}$ to $x_{2}$, and thus $y$ and $y^{\prime}$ lie
along this path and are $k$-centers in $T$.

Let $C_{1}$ be a largest subtree containing an $r$-path such that the vertices
along it with the same distance from the center as $y$ and $y^{\prime}$ (these
in fact are $y$ and $y^{\prime}$ themselves) have degree $2$. Since the
offshoots at $y$ and $y^{\prime}$ have at least $\ell+1$ vertices, $C_{1}$
fits into a card, we see it, and it gives us in full all offshoots from the
path other than those at $y$ and $y^{\prime}$.

The exclusion argument with maximal $k$-vines used in Lemma 5.4 now tells us
the offshoots at $y$ and the offshoots at $y^{\prime}$ but not which subgraph
is attached to which vertex on $P$. If $C_{1}$ is symmetric (under reversal of
the $r$-path), then it does not matter which is which, so we may assume that
$C_{1}$ is not symmetric. Let $Q$ and $Q^{\prime}$ denote the two sets of
offshoots yet to be assigned to $y$ or $y^{\prime}$. (If $y=y^{\prime}$, at
the center of an $r$-path with $r$ being odd, then the exclusion argument for
the maximal $k$-vines gives the offshoots from the center, without needing to
distinguish $Q$ from $Q^{\prime}$; hence we may assume $y\neq y^{\prime}$.)

Since the distance between $x_{1}$ and $x_{2}$ is at most $\ell+5$, and in
this section we know $k-1\geq\ell+3$, both $U_{1}$ and $U_{2}$ contain the
center of $P$. Since we also know the distance between $x_{i}$ and the center,
and $C_{1}$ shows us which path in the inner piece of $U_{i}$ lies along $P$,
from $C_{1}$ we can compute the number $\alpha_{i}$ of vertices in $U_{i}$
that lie in offshoots from $P$ at vertices between $x_{i}$ and the center.
Since $C_{1}$ in fact shows the offshoots from $P$ at all vertices other than
$y$ or $y^{\prime}$, when $\left|V(Q)\right|\neq\left|V(Q^{\prime})\right|$ we
can tell which of $Q$ and $Q^{\prime}$ should be associated with the member of
$\\{y,y^{\prime}\\}$ closer to $x_{1}$ to reach a total of $\alpha_{1}$
vertices on that side.

Hence we may assume $\left|V(Q)\right|=\left|V(Q^{\prime})\right|$. We may
also assume $\alpha_{1}\leq\alpha_{2}$, by symmetry. If
$\alpha_{1}=\alpha_{2}$, then we may assume by symmetry that $U_{1}$ and
$U_{2}$ are indexed so that the outside piece of $U_{2}$ is at least as big as
the outside piece of $U_{1}$. Now let $C_{2}$ be a largest long subtree having
offshoots on one side of the center that agree with $U_{1}$ (as seen in
$C_{1}$), allowing also offshoots at the vertex whose distance from the end
agrees with $y$. Since $C_{2}$ omits at least half of the vertices outside
$P$, and $n-r\geq 2\ell$, we have deleted enough so that $C_{2}$ fits in a
card. We see $C_{2}$, and it tells us which of $Q$ and $Q^{\prime}$ is
attached to the member of $\\{y,y^{\prime}\\}$ in $U_{1}$ (this uses that
$C_{2}$ is asymmetric).

If $\alpha_{1}<\alpha_{2}$, then instead we define $C_{2}$ having an $r$-path
and offshoots at the member of $\\{y,y^{\prime}\\}$ in $U_{1}$ but using only
$\alpha_{1}+1$ of the vertices in offshoots from $P$ at vertices on the side
of the center in $U_{2}$. This distinguishes $y$ and $y^{\prime}$ in $C_{2}$,
which is again small enough to fit into a card and tell us which of $Q$ and
$Q^{\prime}$ is attached to $y$. $\Box$

######  Theorem 5.7.

If $r\geq n-3\ell$ and $n\geq 6\ell+11$, and $S^{\ell+1}\not\subseteq T$, then
$T$ is $\ell$-reconstructible.

###### Proof.

As we have noted, the remaining case is $n-3\ell\leq r\leq n-2\ell-1$ with the
vertices $x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2}$ distinct and occurring in
that order along $P$. Let $d(u,u^{\prime})$ denote the distance between
vertices $u$ and $u^{\prime}$. Since we know $U_{i}$, we know
$d(x_{i},x_{i}^{\prime})$. By symmetry, we may assume
$d(x_{1},x_{1}^{\prime})\leq d(x_{2},x_{2}^{\prime})$.

For $v\in V(P)$, let $f(v)$ be the number of vertices in the offshoots from
$P$ at $v$. We next prove $f(x_{1}^{\prime})+f(x_{2}^{\prime})\geq\ell+1$.
There are $r-2k$ vertices between $x_{1}$ and $x_{2}$ on $P$. The offshoots at
$x_{1}^{\prime}$ and $x_{2}^{\prime}$ contain extremal vertices in $U_{1}$ and
$U_{2}$. The paths from $x_{1}$ and $x_{2}$ to extremal vertices have length
$k-1$. Hence the offshoots at $x_{1}^{\prime}$ and $x_{2}^{\prime}$ together
contain at least $2k-2-(r-2k)$ vertices, due to the order
$(x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2})$. By Lemma 2.12 and the case
$r\geq n-3\ell$ and $n\geq 6\ell+11$,

$4k-r-2\geq 2r-2\ell-8-r-2\geq r-2\ell-10\geq n-5\ell-10\geq\ell+1.$

This completes the proof that $f(x_{1}^{\prime})+f(x_{2}^{\prime})\geq\ell+1$.

Case 1: $d(x_{1},x_{1}^{\prime})=d(x_{2},x_{2}^{\prime})$. In this case
$x_{1}^{\prime}$ and $x_{2}^{\prime}$ are equidistant from the center. Since
we have proved $f(x_{1}^{\prime})+f(x_{2}^{\prime})\geq\ell+1$, Lemma 5.6
implies that $T$ is $\ell$-reconstructible.

Case 2: $d(x_{1},x_{1}^{\prime})<d(x_{2},x_{2}^{\prime})$, by symmetry. Let
$x_{1}^{\prime\prime}$ be the vertex at distance $d(x_{1},x_{1}^{\prime})$
from $x_{2}$ along the path from $x_{2}$ to $x_{1}$. Similarly, let
$x_{2}^{\prime\prime}$ be the vertex at distance $d(x_{2},x_{2}^{\prime})$
from $x_{1}$ along the path from $x_{1}$ to $x_{2}$. The order of the six
vertices along $P$ is
$(x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2}^{\prime\prime},x_{1}^{\prime\prime},x_{2})$
or
$(x_{1},x_{1}^{\prime},x_{2}^{\prime\prime},x_{2}^{\prime},x_{1}^{\prime\prime},x_{2})$,
depending on whether $d(x_{2},x_{2}^{\prime})>d(x_{1},x_{2})/2$.

If $f(x_{1}^{\prime})+f(x_{1}^{\prime\prime})$ or
$f(x_{2}^{\prime})+f(x_{2}^{\prime\prime})$ exceeds $\ell$, then Lemma 5.6
completes the proof. Hence we may assume
$f(x_{1}^{\prime})+f(x_{1}^{\prime\prime})\leq\ell$ and
$f(x_{2}^{\prime})+f(x_{2}^{\prime\prime})\leq\ell$. On the other hand, we
have proved $f(x_{1}^{\prime})+f(x_{2}^{\prime})\geq\ell+1$.

We know the locations of
$x_{1},x_{1}^{\prime},x_{1}^{\prime\prime},x_{2},x_{2}^{\prime},x_{2}^{\prime\prime}$
along $P$. Since $f(x_{1}^{\prime})+f(x_{2}^{\prime})\geq\ell+1$, omitting the
offshoots at the four vertices
$x_{1}^{\prime},x_{1}^{\prime\prime},x_{2}^{\prime},x_{2}^{\prime\prime}$
leaves a long subtree that fits in a card. Hence we see a largest long csc
$C_{1}$ in which the vertices at these specified distances along the $r$-path
have degree $2$; this csc shows us all offshoots at the other vertices.

Since $f(x_{1}^{\prime})+f(x_{1}^{\prime\prime})\leq\ell$ and $r\leq n-2\ell$,
a largest long subtree having offshoots from the $r$-path only at the vertices
having the distances of $x_{1}^{\prime}$ and $x_{1}^{\prime\prime}$ from the
ends of the path fits in a card and shows us the offshoots at $x_{1}^{\prime}$
and $x_{1}^{\prime\prime}$, but not which is at which vertex. Similarly, we
obtain the offshoots at $x_{2}^{\prime}$ and $x_{2}^{\prime\prime}$ but do not
know which set is attached to which vertex.

If $d(x_{2},x_{2}^{\prime})>d(x_{2},x_{1})/2$, then the order along $P$ is
$(x_{1},x_{1}^{\prime},x_{2}^{\prime},x_{2}^{\prime\prime},x_{1}^{\prime\prime},x_{2})$.
In this case the offshoots at $x_{2}^{\prime\prime}$ and
$x_{1}^{\prime\prime}$ appear in $U_{2}$, and we know them because we know all
of $U_{2}$ and which of its major pieces is the inner one. This distinguishes
which set of offshoots in each pair $(x_{1}^{\prime},x_{1}^{\prime\prime})$
and $(x_{2}^{\prime},x_{2}^{\prime\prime})$ is attached to which vertex,
completing the reconstruction of $T$.

Hence we may assume $d(x_{2},x_{2}^{\prime})\leq d(x_{2},x_{1})/2$, and the
six vertices occur in the order
$(x_{1},x_{1}^{\prime},x_{2}^{\prime\prime},x_{2}^{\prime},x_{1}^{\prime\prime},x_{2})$
along $P$, including the possibility $x_{2}^{\prime\prime}=x_{2}^{\prime}$.
Again we can use $U_{2}$ to see the offshoots at $x_{1}^{\prime\prime}$ and
assign offshoots to the pair $(x_{1}^{\prime},x_{1}^{\prime\prime})$, but we
still must assign the offshoots at $x_{2}^{\prime}$ and
$x_{2}^{\prime\prime}$. If $x_{2}^{\prime}=x_{2}^{\prime\prime}$, then there
is only one set of offshoots and no need to distinguish them, so we may assume
$d(x_{2},x_{2}^{\prime})\leq[d(x_{2},x_{1})-1]/2\leq(\ell+4)/2$.

Some offshoot at $x_{2}^{\prime}$ contains a path to an inner extremal vertex
of $U_{2}$. Hence $f(x_{2}^{\prime})\geq k-1-d(x_{2},x_{2}^{\prime})\geq
k-3-\ell/2$. Since $k\geq\ell+4$ (using $n\geq 6\ell+11$), we have
$f(x_{2}^{\prime})\geq\ell/2+1$. Since
$f(x_{2}^{\prime})+f(x_{2}^{\prime\prime})\leq\ell$, we conclude
$f(x_{2}^{\prime})>f(x_{2}^{\prime\prime})$, which allows us to assign the
offshoots to $x_{2}^{\prime}$ and $x_{2}^{\prime\prime}$ correctly, completing
the reconstruction of $T$. $\Box$

##  6 Small Diameter

In this section we consider trees with small diameter, in particular with
$r\leq n-3\ell-1$. First we consider those having sparse cards and then those
not having sparse cards. When $r\leq n-3\ell-1$, any connected card has at
least $2\ell+1$ vertices outside any path.

We note first a case that we have already handled.

######  Corollary 6.1.

If $n\geq 6\ell+5$ and $r\leq n-\ell$ and $T$ contains a sparse card that is a
$3$-legged spider, then $T$ is $\ell$-reconstructible.

###### Proof.

A $3$-legged spider has at most $(3r-1)/2$ vertices. Such a tree as a card
requires $(3r-1)/2\geq n-\ell\geq 5\ell+5$, so $r\geq(10\ell+11)/3$. In
particular, $r\geq 3\ell+6$. By Lemma 2.16, $T$ has exactly one spi-center.
Now Lemma 3.2 applies and $T$ is $\ell$-reconstructible. $\Box$

Henceforth in this section we may assume that $T$ has no sparse card that is a
$3$-legged spider. Since all longest paths in a tree have the same center, the
central vertices of all long cards are the same. An optimal sparse card is a
sparse card such that, among all sparse cards, the primary vertex is closest
to the center.

######  Lemma 6.2.

Suppose $n\geq 6\ell+11$ and $r\leq n-3\ell-1$. Let $C$ with primary vertex
$z$ be an optimal sparse card, having an $r$-path $\langle
v_{1},\ldots,v_{r}\rangle$ with $z=v_{j}$ and $j\leq(r+1)/2$. Every $r$-path
in $T$ contains the path from $z$ to the center of $T$, and all optimal sparse
cards have the same primary vertex $z$ in $T$.

###### Proof.

Since all longest paths in a tree contain the center, when
$j=\left\lfloor{(r+1)/2}\right\rfloor$ there is nothing to prove, so we may
assume $j<\left\lfloor{(r+1)/2}\right\rfloor$. Let $P=\langle
v_{1},\ldots,v_{r}\rangle$.

Let $y$ be the central vertex of $T$ closest to $z$. Let $T^{\prime}$ be the
component of $T-z$ containing $y$. Let $P^{\prime}$ be another $r$-path in
$T$; like every $r$-path, $P^{\prime}$ contains $y$. If $P^{\prime}$ does not
contain the path from $y$ to $z$, then $P^{\prime}$ leaves the path from $y$
to $z$ at some vertex $w$ before $z$. In the direction away from $z$, since
$P^{\prime}$ is a longest path, it extends $\left\lfloor{r/2}\right\rfloor$
vertices beyond $y$ in $T^{\prime}$, just as $P$ does. We now form a sparse
card $C^{\prime}$ with $r$-path $P^{\prime}$ and primary vertex $w$. We keep
$n-\ell-r$ vertices from the component of $C-w$ containing $z$. The number of
vertices in that component is greater than $n-\ell-r$, since it contains $z$
and the offshoots from $P$ at $z$ in $C$, which total $n-\ell-r$ vertices.
Hence $C^{\prime}$ exists. Since $w$ is closer to the center of $T$ than $z$
is, $C^{\prime}$ contradicts the optimality of $C$.

Suppose that distinct vertices $z$ and $z^{\prime}$ are primary vertices in
optimal sparse cards $C$ and $C^{\prime}$, respectively. Since $z$ and
$z^{\prime}$ lie on every $r$-path, the path $R$ joining them is in both $C$
and $C^{\prime}$. If $z$ or $z^{\prime}$ lies outside the central $r-2j+2$
vertices of the designated $r$-path in the other card, then $T$ has a path
with more than $r$ vertices. Otherwise, the offshoots from $R$ at the primary
vertex in $C$ are offshoots from $R$ at a non-primary vertex in $C^{\prime}$,
and vice versa. Since $C$ and $C^{\prime}$ are cards, this yields
$n-\ell-r+j-1\leq\ell+j-1$, which contradicts $r\leq n-3\ell-1$. $\Box$

######  Lemma 6.3.

Suppose $n\geq 6\ell+11$ and $r\leq n-3\ell-1$. If $T$ has a sparse card of
degree $3$, then some optimal sparse card has degree $3$. If no sparse card
has degree $3$, then every sparse card is optimal.

###### Proof.

Let $C$ be any sparse card with primary vertex $z$ on the $r$-path $P$. Let
$P^{\prime}$ be an $r$-path in another sparse card. Since $r\leq n-3\ell-1$,
in any sparse card the offshoots from the $r$-path at the primary vertex have
at least $2\ell+1$ vertices, and the card omits only $\ell$ vertices.

If $P^{\prime}$ contains the path from $z$ to the central vertex $y$, then
there are at most $\ell$ vertices available for offshoots from $P^{\prime}$ at
any vertex of $P^{\prime}$ closer to $y$ than $z$, so such a card could not
have a primary vertex closer to $y$. If $P^{\prime}$ departs from $P$ at some
vertex $w$ before $z$ in traveling from $y$, then the sparse card $C^{\prime}$
formed in the proof of Lemma 6.2 has primary vertex $w$. That card has degree
$3$, since $w$ has degree $2$ in $C$.

That is, if $C$ is not an optimal sparse card, then we obtain a sparse card of
degree $3$ whose primary vertex is closer to the center. This implies both
conclusions claimed. $\Box$

######  Definition 6.4.

Peripheral vertices are endpoints of $r$-paths in $T$. When $T$ has a sparse
card, let $z$ denote the unique vertex of $T$ that by Lemma 6.2 is the primary
vertex in every optimal sparse card. The primary value of $T$ is the index $j$
with $j\leq(r+1)/2$ such that $z$ is $v_{j}$ on an $r$-path $P$ indexed as
$\langle v_{1},\ldots,v_{r}\rangle$.

For a given optimal sparse card $C$, let $W$ denote the union of the offshoots
from $P$ at $z$ in $C$, with $W^{*}$ being the union of the components of
$T-z$ containing the offshoots in $W$. Let $T_{1}$ and $T_{2}$ be the
components of $T-z$ containing $v_{j-1}$ and $v_{j+1}$, respectively, where
$j$ is the primary value. Although we see $W$ in $C$, from $C$ we do not know
any of $W^{*}$, $T_{1}$, or $T_{2}$.

When $T$ has a sparse card and primary value $j$, a long-legged card is a
connected card $C^{\prime}$ having a leg of length more than $r-j$. When
$r\leq n-3\ell-1$, a long-legged card has a branch vertex, since otherwise the
card is a path, requiring $r\geq n-\ell$. See Figure 6.

Figure 6: Sparse card $C$ and long-legged card $C^{\prime}$

######  Lemma 6.5.

Suppose $n\geq 6\ell+11$ and $r\leq n-3\ell-1$. If $T$ has a sparse card of
degree $3$, and $T$ has a long-legged card, then $T$ is
$\ell$-reconstructible.

###### Proof.

By Lemma 6.3, $T$ has an optimal sparse card $C$ of degree $3$. Relative to
$C$, we use notation $z,j,P,T_{1},T_{2},W,W^{*}$ as in Definition 6.4. Since
$C$ has degree $3$, $W$ is a single offshoot from $P$. Since $C$ is a card and
$r<n-3\ell$, in $W$ there are at least $2\ell+1$ vertices. Let $q$ be the
maximum length of the legs in long-legged cards, so $q>r-j$. Let
${\mathcal{C}}^{\prime}$ be the family of long-legged cards having a leg of
length $q$. For a fixed card $C^{\prime}\in{\mathcal{C}}^{\prime}$, let $L$ be
the leg of length $q$, ending at branch vertex $x$, and let
$X=C^{\prime}-V(L-x)$, as shown in Figure 6. Let $X^{*}$ be the component of
$T-V(L-x)$ containing $x$.

Step 1: The primary vertex $z$ in $C$ is on $L$ in $C^{\prime}$, at distance
$r-j$ from the leaf of $L$, and $X\subseteq W^{*}$. Also, $x$ and $X^{*}$ are
independent of the choice of $C^{\prime}$ in ${\mathcal{C}}^{\prime}$, and
$j-1\leq\ell$.

We first prove $z\in V(L)$. Suppose not. Let $z^{\prime}$ be the vertex of
$C^{\prime}$ closest to $z$ in $T$, and let $R$ be the path from $z$ to
$z^{\prime}$. Since no path with length more than $r-j$ starts at $z$, we
cannot have $z^{\prime}\in V(X)$ (and hence also $z\notin V(X)$), and for the
same reason $z^{\prime}$ lies on $L$ within distance $r-j$ of the leaf in $L$.
Let $L^{\prime}$ be the portion of $L$ from $z^{\prime}$ to the leaf end of
$L$.

Since $\left|V(W)\right|\geq 2\ell+1$ and $C^{\prime}$ omits only $\ell$
vertices, $W$ intersects $C^{\prime}$. Since $T$ has no cycles and $z$ has a
neighbor in $W$, the neighbor of $z$ on $R$ must be the neighbor of $z$ in
$W$. Hence $P$ lies completely outside $C^{\prime}$, since otherwise $T$ has
paths from $z$ to $C^{\prime}$ through $P$ and through $W$. Now
$L^{\prime}\cup R\cup\langle v_{j},\ldots,v_{r}\rangle$ is a path. If
$L^{\prime}$ has length at least $j$, then this path is longer than $P$. If
$L^{\prime}$ has length less than $j$, then replacing $L^{\prime}$ with
$R\cup\langle v_{j},\ldots,v_{r}\rangle$ and deleting some vertices of $X$
yields a long-legged card having a longer leg than $C^{\prime}$. Both
possibilities are forbidden, so in fact $z=z^{\prime}\in V(L-x)$.

We have already observed that $L^{\prime}$, ending at $z$, has length at most
$r-j$. Since $z$ has degree $2$ in $C^{\prime}$, the card $C^{\prime}$ has
vertices in two components of $T-z$, and $X$ is contained in one of them.
Since $C^{\prime}$ is a card, $X$ has at least $2\ell+1$ vertices outside any
path, but the only component of $T-z$ having more than $\ell$ vertices outside
$P$ is $W^{*}$. Hence $X\subseteq W^{*}$, and the neighbor of $z$ on the path
to $x$ is not in $P$. If $L^{\prime}$ has length less than $r-j$, we can now
replace $L^{\prime}$ in $C^{\prime}$ with a path of length $r-j$ from $z$ in
$P$ and delete vertices from $X$ to obtain a long-legged card with leg longer
than $C^{\prime}$, which contradicts the choice of $C^{\prime}$. Hence
$L^{\prime}$ has length exactly $r-j$.

Suppose that there are choices for $C^{\prime}$ with two different branch
vertices playing the role of $x$ at the end of the leg of length $q$. Both
have distance $q-r+j$ from $z$, so neither of these vertices is on the path
from $z$ to the other. Hence the paths to them from $z$ diverge. Both cards
now contain at least $2\ell+1$ vertices of $W^{*}$ outside a longest path that
do not appear in the other, which prevents the cards from having $n-\ell$
vertices. Hence there is only one choice for $x$. Since $x$ is independent of
the choice of $C^{\prime}$ in ${\mathcal{C}}^{\prime}$, and $z$ has fixed
distance $r-j$ from the end of $L$, the subtree $X^{*}$ also is independent of
the choice of $C^{\prime}$. Furthermore, since $X\subseteq W^{*}$, also
$X^{*}\subseteq W^{*}$. This and $z$ having degree $2$ in $C^{\prime}$ imply
that the card $C^{\prime}$ omits at least $j-1$ vertices of $P$, so
$j-1\leq\ell$.

Step 2: Let ${\hat{C}}$ be a csc of $T$ having a leg ${\hat{L}}$ of length at
least $q$, let ${\hat{x}}$ be the branch vertex of ${\hat{C}}$ at the end of
${\hat{L}}$, and let ${\hat{X}}={\hat{C}}-V({\hat{L}}-{\hat{x}})$. If
${\hat{C}}$ has at least $\ell-j+2$ vertices in offshoots from its longest
path, then ${\hat{X}}\subseteq X^{*}$.

Let ${\hat{q}}$ be the length of ${\hat{L}}$. Every longest path in
${\hat{C}}$ contains ${\hat{L}}$, since ${\hat{q}}\geq r-j$. Let
${\hat{x}}^{\prime}$ be the vertex of $C^{\prime}$ at which the path from
${\hat{x}}$ to $V(C^{\prime})$ reaches $C^{\prime}$; it may be in $X$ or in
$L-x$.

First suppose ${\hat{x}}^{\prime}\in V(X)$. In this case that the path
${\hat{R}}$ from ${\hat{x}}$ to $x$ lies entirely in $X^{*}$ and uses no edge
of $L$. If $x\in{\hat{X}}$, then both ${\hat{x}}$ and $x$ lie in ${\hat{X}}$,
so also ${\hat{R}}$ lies within ${\hat{X}}$ and uses no edge of ${\hat{L}}$.
Thus ${\hat{R}}$ meets $L$ at $x$ and ${\hat{L}}$ at ${\hat{x}}$, and the
union $L\cup{\hat{R}}\cup{\hat{L}}$ is a path longer than $P$. On the other
hand, if $x\notin{\hat{X}}$, then ${\hat{X}}\cap C^{\prime}$ is contained in
the component of $C^{\prime}-x$ that contains ${\hat{x}}^{\prime}$. Now
${\hat{X}}$ lies in the component of $T-x$ containing ${\hat{x}}^{\prime}$,
which is $X^{*}$, as desired.

The remainder of this step consists of showing that the other case
${\hat{x}}^{\prime}\notin V(X)$ cannot occur. Suppose
${\hat{x}}^{\prime}\notin V(X)$, which implies ${\hat{x}}^{\prime}\in V(L-x)$.
We first prove ${\hat{x}}^{\prime}\in V({\hat{X}})$. Since ${\hat{x}}\in
V({\hat{X}})$ and since ${\hat{x}}^{\prime}$ is where ${\hat{R}}$ reaches
$C^{\prime}$, the assumption ${\hat{x}}^{\prime}\notin V({\hat{X}})$ puts all
of ${\hat{X}}$ outside $C^{\prime}$, including the $\ell+2-j$ vertices of
${\hat{C}}$ that have been assumed to lie in offshoots from a longest path in
${\hat{C}}$. Also, since $z\in V(L-x)$, the card $C^{\prime}$ lacks at least
$j-1$ vertices of $P$ from $T_{1}$ or $T_{2}$. We now have at least $\ell+1$
vertices missing from the card $C^{\prime}$, a contradiction. Thus
${\hat{x}}^{\prime}\in V({\hat{X}})$.

We next prove ${\hat{x}}\in V(C^{\prime})$, which is equivalent to
${\hat{x}}={\hat{x}}^{\prime}$. Suppose ${\hat{x}}\neq{\hat{x}}^{\prime}$.
Since ${\hat{x}}^{\prime},{\hat{x}}\in{\hat{X}}$, the path
${\hat{R}}^{\prime}$ joining ${\hat{x}}^{\prime}$ and ${\hat{x}}$ lies
entirely in ${\hat{X}}$. Since ${\hat{L}}$ contains no vertex of ${\hat{X}}$
other than ${\hat{x}}$, the assumption ${\hat{x}}\neq{\hat{x}}^{\prime}$
implies that ${\hat{L}}$ shares no vertices with $L$. Let $L^{\prime\prime}$
be the part of $L$ from ${\hat{x}}^{\prime}$ to the leaf in $C^{\prime}$.
Since ${\hat{q}}\geq q$, replacing $L^{\prime\prime}$ with
${\hat{R}}\cup{\hat{L}}$ (and deleting some of $V(X)$) yields a card with a
longer leg than $C^{\prime}$. Hence ${\hat{x}}={\hat{x}}^{\prime}$, which
yields ${\hat{x}}\in V(L)$.

Now we consider how ${\hat{L}}$ departs from ${\hat{x}}$, in three cases. (1)
If ${\hat{L}}$ does not depart ${\hat{x}}$ along $L$, then either
$L^{\prime\prime}\cup{\hat{L}}$ is a path longer than $P$, or replacing
$L^{\prime\prime}$ with ${\hat{L}}$ contradicts the choice of $C^{\prime}$
(this uses $q\geq r-j$). (2) If ${\hat{L}}$ departs ${\hat{x}}$ along
$L^{\prime\prime}$, then replacing $L^{\prime\prime}$ with ${\hat{L}}$ yields
a card with a longer leg than $C^{\prime}$, since ${\hat{q}}\geq q$. (3) We
may therefore assume that ${\hat{L}}$ departs ${\hat{x}}$ along $L$ toward
$x$. Since $L^{\prime\prime}\cup{\hat{L}}$ cannot be longer than $P$, vertex
${\hat{x}}$ must be farther from $X$ than $z$. In this case, the $\ell-j+2$
vertices of ${\hat{C}}$ (in ${\hat{X}}$) in offshoots from its longest path
are omitted from $C^{\prime}$, along with at least $j-1$ vertices from $P$ in
$T_{1}$ or $T_{2}$. This contradicts that $C^{\prime}$ omits exactly $\ell$
vertices. The contradiction arose under the assumption
${\hat{x}}^{\prime}\notin V(X)$, which means that only the earlier case
${\hat{x}}^{\prime}\in V(X)$ occurs, where we proved ${\hat{X}}\subseteq
X^{*}$.

Step 3: Reconstruction of $T-V(X^{*}-x)$. Recall that ${\mathcal{C}}^{\prime}$
is the family of long-legged cards having a leg of length $q$. For any
$C^{\prime}\in{\mathcal{C}}^{\prime}$, we have $X\subseteq W^{*}$ by Step 1,
and hence $X^{*}\subseteq W^{*}$. Also by Step 1, the branch vertex $x$ at the
end of the leg is the same in all such $C^{\prime}$. We have also observed
that every such card $C^{\prime}$ omits at least $j-1$ vertices from $P$, so
$j-1\leq\ell$. Choose $C^{\prime}\in{\mathcal{C}}^{\prime}$ to maximize the
length of the longest offshoot from the leg $L$ at $x$; let $t^{\prime}$ be
this maximum length. We also know that $C^{\prime}$ has at least $2\ell+1$
vertices outside its longest path. Therefore, in $C^{\prime}$ we can find a
subtree $U$ with a leg $L$ of length $q$ ending at branch vertex $u$ such that
$U$ contains a path of length $t^{\prime}$ from $u$ outside $L$ plus exactly
$\ell+1$ other vertices in the offshoots from $L$ at $u$. Any such subtree $U$
is a particular choice of ${\hat{C}}$ in Step 2, so $u\in X^{*}$. Furthermore,
since $U$ has the maximum possible length beyond $u$, we must have $u=x$, and
the offshoots in $U$ are contained in $X^{*}$ and $W^{*}$.

Now let $C_{1}$ be a largest subtree in $T$ that contains $U$ but attaches no
additional vertices of $X^{*}$ to any vertex of $U$. By Step 2, any $C_{1}$
grown from $U$ in this way must have $u=x$, and its $\ell+1$ vertices in
offshoots outside the specified path extending the leg by length $t^{\prime}$
are contained in $X^{*}$ and $W^{*}$. Therefore, $C_{1}$ omits at least $\ell$
vertices from the set of at least $2\ell+1$ such vertices in $X$. Thus $C_{1}$
fits in a card. Therefore in $C_{1}$ we see all the offshoots from $L-x$ in
full, giving us all of $T$ outside $X^{*}$.

Step 4: Reconstruction of $X^{*}$. It remains to determine the offshoots from
$x$ that comprise $X^{*}$. Among the cards in ${\mathcal{C}}^{\prime}$, which
all have the same vertex $x$ at the end of the long leg, choose $C^{\prime}$
to minimize $d_{C^{\prime}}(x)$, and among those choices choose $C^{\prime}$
to minimize the size of a smallest offshoot $Y$ in $C^{\prime}$ from $L$ at
$x$. If some offshoot in $T$ at $x$ other than $Y$ appears only partially in
$C^{\prime}$, then we can alter $C^{\prime}$ to add a vertex from that
offshoot and delete a vertex from $Y$. If this eliminates $Y$, then either the
degree of the branch vertex at the end of the leg decreases or we obtain a
long-legged card with a longer leg. Hence in $C^{\prime}$ we see in full all
offshoots from $L$ in $T$ at $x$ that have any vertices in $C^{\prime}$,
except possibly the one containing $Y$. We must find the remaining offshoots
from $x$ in $T$.

Fixing this $C^{\prime}$ and hence $X$, let $d$ be the degree of $x$ in $X$,
and let $Q_{1},\ldots,Q_{d}$ be the offshoots from $x$ in $X$, in
nonincreasing order of size (here $Q_{d}=Y$). Note $d\geq 2$, since $x$ is a
branch vertex in $C^{\prime}$. As observed above, the offshoots
$Q_{1},\ldots,Q_{d-1}$ from $x$ in $C^{\prime}$ are offshoots from $x$ in $T$,
seen in full in $C^{\prime}$.

Since $C^{\prime}$ is a card, $Q_{1},\ldots,Q_{d}$ together have at least
$2\ell+1$ vertices outside any path, so they have at least $2\ell+2$ vertices
in total. Let ${\mathcal{C}}_{1}$ be the family of subtrees having a leg of
length $q$ and $d-1$ offshoots at the end of the leg, with $d-2$ of them being
$Q_{1},\ldots,Q_{d-2}$. Every member of ${\mathcal{C}}_{1}$ fits in a card,
since otherwise there would be a choice for $C^{\prime}$ with $x$ having
degree less than $d$ in $X$.

Case 1: $d\geq 4$. Since $Q_{1},\ldots,Q_{d-2}$ are the largest offshoots in
$X$ and include at least half of the offshoots, they together have at least
$\ell+1$ vertices, and since the longest path from $x$ in $X$ has length at
most $j-2$, these offshoots have at least $\ell-j+3$ vertices outside a
longest path in $C^{\prime}$. The union of these offshoots with the leg
satisfies the conditions for ${\hat{C}}$ in Step 2, in every subtree in
${\mathcal{C}}_{1}$ the branch vertex at the end of the leg is in $X$, and it
must equal $x$ because moving farther into $X$ would not allow having an
offshoot as large as $Q_{1}$.

We have noted that every member of ${\mathcal{C}}_{1}$ fits in a card. A
largest member of ${\mathcal{C}}_{1}$ shows us $Q_{d-1}$ or another offshoot
of the same size as its smallest offshoot. We know the multiplicity of each
such csc, since we know $T_{1}$ and $T_{2}$ and hence the number of peripheral
vertices in each. Thus we also know all the members of ${\mathcal{C}}_{1}$ in
which the smallest offshoot is obtained by deleting vertices of $Q_{d-1}$ (or
another offshoot of the same size). After excluding those members, a largest
remaining member of ${\mathcal{C}}_{1}$ shows us the next largest offshoot at
$x$. Continuing the exclusion argument allows us to find all the offshoots at
$x$ (there may be more than $d$).

Case 2: $d=3$. In $C^{\prime}$ we see $Q_{1}$ and $Q_{2}$; these are offshoots
in $T$ seen in full in $C^{\prime}$. Since $Q_{1}\cup Q_{2}\cup Q_{3}$ has at
least $2\ell+2$ vertices and $Q_{1}$ is no smaller than $Q_{2}$, together
$Q_{1}$ and $Q_{3}$ have at least $\ell+1$ vertices. By the minimality of $Y$,
the extension $Q^{*}_{3}$ of $Q_{3}$ in $T$ is no bigger than $Q_{2}$. Recall
that every member of ${\mathcal{C}}_{1}$ fits in a card. Since we know $Q_{2}$
and the number of peripheral vertices in $T_{2}$ (and in $T_{1}$ if
$j=(r+1)/2$), we can exclude from ${\mathcal{C}}_{1}$ all the members whose
second offshoot arises by deleting vertices of $Q_{2}$ (with multiplicity). A
largest remaining member shows us the full $Q^{*}_{3}$. Continuing the
exclusion argument allows us to find the remaining offshoots at $x$.

Case 3: $d=2$. We know $Q_{1}$ as a full offshoot in $T$, but we do not see in
full the next-largest offshoot from $x$ in $T$ (unless it has the same size as
$Q_{1}$ and we have several choices for $C^{\prime}$). Let $Q_{2}^{*}$ be this
offshoot in $T$. A card $C_{2}\in{\mathcal{C}}^{\prime}$ having two offshoots
$Y_{1}$ and $Y_{2}$ as equal in size as possible shows us $Q_{2}^{*}$ as
$Y_{2}$ if the sizes of the two offshoots differ by more than $1$, after which
we can use exclusion to find any smaller offshoots.

Hence we may assume that the sizes of $Y_{1}$ and $Y_{2}$ in $C_{2}$ differ by
at most $1$. In particular,
$\left|V(Y_{2})\right|=\left\lfloor{(n-\ell-q-1)/2}\right\rfloor$. With $q\geq
r-j+1$ and $r\leq n-3\ell-1$, we have $n-q\geq n-r+j-1\geq 3\ell+j$. Hence

$\left|V(Y_{2})\right|=\left\lfloor{(n-\ell-q-1)/2}\right\rfloor\geq\left\lfloor{(2\ell+j-1)/2}\right\rfloor>\ell,$

where the last inequality uses $j\geq 2$. Offshoots from $L$ at $x$ in $T$
that do not contain $Y_{1}$ or $Y_{2}$ are completely omitted from $C_{2}$.
Hence in total they have at most $\ell$ vertices and are smaller than $Y_{2}$.

Because $X^{*}$ is an offshoot from a vertex in an offshoot from $z$, it has
length at most $j-2$. Since in Step 1 we showed $j-1\leq\ell$, the length of
$X^{*}$ is less than $\ell$. Since $Y_{1}$ and $Y_{2}$ each have more than
$\ell$ vertices and $X^{*}$ has length less than $\ell$, we can choose $C_{2}$
so that $Y_{1}$ and $Y_{2}$ each have the largest possible length, and it will
be the length of the offshoots from $x$ containing them in $T$. We determined
this maximum length $t^{\prime}$ from $C^{\prime}$ in Step 3. We see in
$C_{2}$ how many members of $\\{Y_{1},Y_{2}\\}$ have length $t^{\prime}$.
Since we know $Q_{1}$, we know whether it has length $t^{\prime}$. By knowing
how many members of $\\{Y_{1},Y_{2}\\}$ have length $t^{\prime}$, since they
have the same length as the offshoots $Q_{1}$ and $Q_{2}^{*}$ in $T$ that
contain them, we know also whether $Q_{2}^{*}$ has length $t^{\prime}$.

If $Q_{2}^{*}$ has length $t^{\prime}$, then let ${\mathcal{C}}_{3}$ be the
family of subtrees of $T$ having a leg of length $q$ at the end of which is a
single offshoot that has length $t^{\prime}$ and has at least
$\left|Y_{2}\right|$ vertices. In every member of ${\mathcal{C}}_{3}$, the
vertex at distance $q$ from the leaf of the leg is $x$. If also $Q_{1}$ has
length $t^{\prime}$, then in some members of ${\mathcal{C}}_{3}$ the offshoot
arises by deleting vertices from $Q_{1}$. Since we know $Q_{1}$ and the number
of peripheral vertices outside $Q_{1}$, we can exclude any such members, and a
largest remaining member of ${\mathcal{C}}_{3}$ shows us $Q_{2}^{*}$.

If $Q_{2}^{*}$ has length less than $t^{\prime}$, then let
${\mathcal{C}}^{\prime}_{3}$ be the family of subtrees of $T$ having a leg of
length $q$ at the end of which are two offshoots: one being a path of length
$t^{\prime}$ and one having $\left|V(Y_{2})\right|$ vertices. Because
$\left|V(Y_{2})\right|>\ell$, the branch vertex must be $x$. Because we know
$Q_{1}$, the number of paths of length $q+t^{\prime}$, and the number of
peripheral vertices in $T_{2}$ (and $T_{1}$ if $j=(r+1)/2$), we can exclude
the members of ${\mathcal{C}}^{\prime}_{3}$ in which the offshoot with
$\left|V(Y_{2})\right|$ vertices comes from $Q_{1}$. A largest remaining
member of ${\mathcal{C}}^{\prime}_{3}$ shows us $Q_{2}^{*}$.

Now that we know $Q_{1}$ and $Q_{2}^{*}$, we obtain the remaining offshoots at
$x$ to reconstruct $T$. If $\left|V(Q_{2})\right|\geq\ell$, then let
${\mathcal{C}}_{4}$ be the family of subtrees of $T$ having a leg of length
$q$ at the end of which are two offshoots, one being $Q_{1}$. The presence of
$Q_{1}$ fixes the branch vertex as $x$. Since we know $Q_{2}^{*}$, and all the
smaller offshoots at $x$ together have at most $\ell$ vertices, successively
excluding the members of ${\mathcal{C}}_{4}$ in which the second offshoot
comes from a known offshoot at $x$ allows us to find all the offshoots at $x$.

If $\left|V(Q_{2})\right|<\ell$, then there may be multiple offshoots at $x$
that are bigger then the $Q_{2}$ we see in $C^{\prime}$. In this case let
${\mathcal{C}}^{\prime}_{4}$ be the family of subtrees of $T$ having a leg of
length $q$ at the end of which are two offshoots: one showing exactly $\ell+1$
vertices from $Q_{1}$ including a path of length $q_{1}$, where $q_{1}$ is the
length of $Q_{1}$. This offshoot can only be from $Q_{1}$, and the branch
vertex is fixed at $x$. Having $\left|V(Q_{2})\right|$ or fewer vertices in
the second offshoot still fits in a card. Since we know $Q_{2}^{*}$, we can
therefore employ an exclusion argument using ${\mathcal{C}}^{\prime}_{4}$ to
find the remaining offshoots at $x$. $\Box$

We maintain the definitions and notation from Definition 6.4. By Corollary
6.1, we can reconstruct $T$ if some sparse card is a $3$-legged spider. Hence
when $S^{(r-1)/2}$ is contained in $T$, we may assume that it fits in a card,
and from the deck we can recognize its presence.

######  Lemma 6.6.

Let $T$ be a tree with $n\geq 6\ell+11$ and $r\leq n-3\ell-1$ that has a
sparse card, with optimal sparse cards having primary vertex $z$ and primary
value $j$, and let $t$ be the maximum length of offshoots from $P$ in an
optimal sparse card.

(a) $T$ has a long subtree $C_{0}$ with $r$-path $P^{\prime}$ having vertices
$u_{1},\ldots,u_{r}$ such that offshoots from $P^{\prime}$ at $u_{j}$ in
$C_{0}$ together have at least $\ell+1$ vertices and offshoots from
$P^{\prime}$ in $C_{0}$ at other vertices have at most $\ell$ vertices.
Furthermore, any such subtree $C_{0}$ satisfies $u_{j}=z$.

(b) If a subtree $C_{0}^{\prime}$ with the properties of $C_{0}$ has exactly
$\ell+1$ vertices in offshoots from $P^{\prime}$ at $u_{j}$, then
$C_{0}^{\prime}$ fits in a card. Furthermore, a largest such $C_{0}^{\prime}$
shows in full the component of $T-z$ containing $u_{j+1}$. If $t<j-1$, then it
also shows the component containing $u_{j-1}$.

(c) If $T$ has a sparse card with degree $3$, then $T$ has a subtree $C_{1}$
as in (a) such that also the first branch vertex on $P^{\prime}$ is $u_{j}$
and one of the offshoots from $P^{\prime}$ at $u_{j}$ has exactly $\ell+1$
vertices (others have at most $\ell$ vertices.) Furthermore, if $j<(r+1)/2$ or
$S^{(r-1)/2}\not\subseteq T$, then the component of $T-z$ containing $u_{j+1}$
is seen in full in a largest such $C_{1}$.

###### Proof.

Let $W$ be the union of the offshoots from $P$ in an optimal sparse card $C$.
If $T$ has a sparse card of degree $3$, then we may assume that $C$ has degree
$3$ and $W$ is a single offshoot, by Lemma 6.3. As in Definition 6.4, we have
$z=v_{j}$ with $P=\langle v_{1},\ldots,v_{r}\rangle$.

Note first that subtrees with the properties required for $C_{0}$ and $C_{1}$
exist. Simply include $P$ and exactly $\ell+1$ vertices from $W$ (offshoots
from $P$ at $v_{j+1},\ldots,v_{r}$ may be included but are not needed). Here
$z$ serves as $u_{j}$ and is the first branch vertex on $P$, which serves as
$P^{\prime}$.

Proof of (a). Consider such a subtree $C_{0}$, and let $W^{\prime}$ be the
subgraph of $C_{0}$ induced by the vertices in offshoot(s) from $P^{\prime}$
at $u_{j}$. If $u_{j}\notin V(P)$, then to avoid having a path longer than
$P$, the path from $u_{j}$ to $V(P)$ must start along $u_{j}u_{j+1}$ and reach
$P$ at a vertex other than $z$. This puts $W^{\prime}$ into an offshoot from
$P$ not at $z$. Such offshoots have at most $\ell$ vertices, but $W^{\prime}$
has more than $\ell$ vertices; we conclude $u_{j}\in V(P)$. If $u_{j}\in
V(P)-\\{z,v_{r+1-j}\\}$, then we can choose paths from $P$ and $P^{\prime}$
ending at $u_{j}$ whose union is a path longer than $P$; that is, when
$u_{j}\in\\{v_{j+1},\ldots,v_{r-j}\\}$ we replace $\langle
u_{1},\ldots,u_{j}\rangle$ in $P^{\prime}$ with part of $P$ that is longer,
and when $u_{j}\notin\\{v_{j},\ldots,v_{r+1-j}\\}$ we replace the shorter
portion of $P$ with part of $P^{\prime}$ that is longer. Hence
$u_{j}\in\\{z,v_{r+1-j}\\}$. If $u_{j}=v_{r+1-j}$ with $j\neq(r+1)/2$, then
$W^{\prime}$ plus at least $r-j$ vertices of $P^{\prime}$ lie in $T_{2}$,
contradicting that $T_{2}$ has at most $\ell+r-j$ vertices. Hence $u_{j}=z$.

Proof of (b). By part (a), $u_{j}=z$ in $C_{0}^{\prime}$. Since $t<j-1$ and
$u_{j}=z$, the path $P^{\prime}$ cannot enter $W$. Since $T$ has at most
$\ell$ vertices outside $C\cup W^{*}$, the offshoots $W^{\prime}$ from
$P^{\prime}$ at $u_{j}$ in $C_{0}^{\prime}$ must lie in $W^{*}$. Since $r\leq
n-3\ell-1$, the offshoot $W^{*}$ has at least $2\ell+1$ vertices, so
$C_{0}^{\prime}$ omits at least $\ell$ vertices from $W^{*}$ and fits in a
card. Outside $W^{\prime}$, a largest such $C_{0}^{\prime}$ shows us
everything in $T$ except $W^{*}$ and other offshoots at $z$.

Proof of (c). Recall that we use $T_{2}$ to denote the component of $T-z$
containing $v_{j+1}$. Consider $C_{1}$, in which $u_{j}=z$ by part (a). Let
$W^{\prime}$ denote the offshoot from $P^{\prime}$ at $z$ in $C_{1}$ that has
$\ell+1$ vertices. In the case $j<(r+1)/2$, any path of length $r-j$ extending
from $z$ lies in $T_{2}$, so $u_{j+1},\ldots,u_{r}\in V(T_{2})$. Because
$u_{j}$ is the first branch vertex on $P^{\prime}$, the subset of $V(C_{1})$
consisting of $u_{1},\ldots,u_{j-1}$ and $V(W^{\prime})$ contains exactly