Shockingly, after back and forth with 5.5 Pro and Fable, and about 20 bucks in credits, and verifying up to $n \lesssim 20$, and forcing the models to double-check their work, I got a solution.

<spoiler summary="Solution">

Let $T$ be a tree on $n$ vertices and let $\mu = \mu(T)$ denote the size of a maximum matching of $T$. The minimum size the tree can be reduced to equals

$$
\mathrm{answer} = n - 3\cdot\min\left(\left\lfloor \frac{n-1}{3}\right\rfloor,\ \max(\mu - 1, 0)\right).
$$

Equivalently: if $\mu - 1 \ge \lfloor (n-1)/3 \rfloor$ the answer is $\big((n-1) \bmod 3\big) + 1$, and otherwise the answer is $n - 3\mu + 3$. Since $\mu(T)$ is computable in $O(n)$ on a tree, the whole algorithm is linear.

\textbf{CONVENTIONS}

A chain of four nodes is a simple path $a-b-c-d$ on $4$ distinct vertices of the current graph. The operation contracts $S = \{a,b,c,d\}$ into a single new vertex $v$: $v$ becomes adjacent to exactly those vertices outside $S$ that had at least one neighbor in $S$; adjacencies among vertices outside $S$ are unchanged. One operation removes exactly $3$ vertices.

\textbf{LEMMA 0 (contraction is well behaved).} Let $T$ be a tree and $S$ the vertex set of a $4$-vertex path. Then: (i) every $y \notin S$ has at most one neighbor in $S$; (ii) the result $T'$ is a tree on $n - 3$ vertices; (iii) two vertices outside $S$ are adjacent in $T'$ iff they are adjacent in $T$.

Proof. (i) If $y \notin S$ had two neighbors $p, q \in S$, then the edges $yp, yq$ together with the path from $p$ to $q$ inside the connected set $S$ would form a cycle in $T$. (iii) holds by definition of contraction. For (ii): the induced subgraph of $T$ on $S$ contains exactly the $3$ path edges (a fourth edge inside $S$ would close a cycle). Hence $T'$ has $n-3$ vertices and, by (i) and (iii), exactly $(n-1) - 3 = n - 4$ edges (no two edges of $T$ merge into one). $T'$ is connected, being a contraction image of a connected graph, and a connected graph with $|V| - 1$ edges is a tree. $\blacksquare$

Consequently every intermediate graph is again a tree, so the process is well defined. Note also: an operation is available iff the current tree contains a path on $4$ vertices, and such a path contains two disjoint edges, so an operation is available only if the current matching number is at least $2$.

\textbf{LEMMA S (survival lemma).} Let $M$ be a matching of $T$, let $S$ be the vertex set of the contracted path, and let $M_S \subseteq M$ be the set of edges of $M$ with at least one endpoint in $S$. Then $\mu(T') \ge |M| - |M_S|$. Moreover, if some edge of $M_S$ has an endpoint outside $S$, then $\mu(T') \ge |M| - |M_S| + 1$.

Proof. Every edge of $M \setminus M_S$ has both endpoints outside $S$, hence by Lemma 0(iii) it is an edge of $T'$; these edges form a matching of $T'$ of size $|M| - |M_S|$ that does not cover $v$. If $xy \in M_S$ with $x \in S$ and $y \notin S$, then $y$ is adjacent to $v$ in $T'$; also $y$ is not covered by $M \setminus M_S$ (in $M$ it is covered only by $xy$), and $v$ is not covered. So we may add the edge $vy$. $\blacksquare$

\textbf{LEMMA 1 (every operation destroys a matching edge).} If $T'$ is obtained from $T$ by one operation, then $\mu(T') \le \mu(T) - 1$.

Proof. Let $M'$ be a maximum matching of $T'$ and let $S = \{a,b,c,d\}$ with path edges $ab, bc, cd$. At most one edge of $M'$ is incident to $v$. Lift $M'$ to $T$: every edge of $M'$ avoiding $v$ joins two vertices outside $S$ and is an edge of $T$ by Lemma 0(iii); the edge $vy \in M'$ (if it exists) is replaced by $py$, where $p \in S$ is a neighbor of $y$ in $T$. The lifted set $N$ is a matching of $T$ with $|N| = |M'|$ covering at most one vertex of $S$. That vertex lies in at most one of the disjoint pairs $\{a,b\}$ and $\{c,d\}$, so at least one of the edges $ab$, $cd$ is vertex-disjoint from $N$; adding it yields a matching of $T$ of size $|M'| + 1$. Hence $\mu(T) \ge \mu(T') + 1$. $\blacksquare$

\textbf{COROLLARY (upper bound).} If $k$ operations are performed starting from $T$ with $n \ge 2$, then

$$
k \le \min\left(\left\lfloor \frac{n-1}{3}\right\rfloor,\ \mu(T) - 1\right).
$$

Proof. Each operation removes exactly $3$ vertices and at least one vertex remains, so $3k \le n - 1$. For the second bound assume $k \ge 1$ (for $k = 0$ both bounds are $\ge 0$ since $\mu \ge 1$ when $n \ge 2$). By Lemma 1, the tree present before the $k$-th operation has matching number at most $\mu(T) - (k-1)$; since an operation is performed on it, it contains a $4$-vertex path and thus has matching number at least $2$. Hence $\mu(T) - (k-1) \ge 2$, i.e. $k \le \mu(T) - 1$. $\blacksquare$

\textbf{LEMMA 2 (a good move when there is no perfect matching).} If $T$ has no perfect matching and $\mu(T) \ge 2$, then some operation produces $T'$ with $\mu(T') \ge \mu(T) - 1$.

Proof. First note $T$ is not a star: all edges of a star share the center, so a star has $\mu = 1$.

Fix a maximum matching $M$, $|M| = \mu$. Since $T$ has no perfect matching, $n > 2\mu$, so some vertex $u_0$ is unmatched. Let $u_1$ be any neighbor of $u_0$. If $u_1$ were unmatched, $M \cup \{u_0u_1\}$ would be a larger matching; so $u_1u_2 \in M$ for some $u_2$, and $u_2 \ne u_0$ since $u_0$ is unmatched.

In each case below we exhibit a path on $4$ distinct vertices with vertex set $S$ such that either $|M_S| = 1$, or $|M_S| = 2$ and some edge of $M_S$ has an endpoint outside $S$. By Lemma S this gives $\mu(T') \ge \mu - 1$.

Case A: $\deg(u_2) \ge 2$. Pick a neighbor $x \ne u_1$ of $u_2$. Then $x \ne u_0$ (otherwise $u_0u_1u_2u_0$ would be a cycle), so $P = (u_0, u_1, u_2, x)$ is a path on $4$ distinct vertices. The vertex $u_0$ is unmatched and $u_1, u_2$ are covered only by $u_1u_2 \in M_S$. If $x$ is unmatched, $M_S = \{u_1u_2\}$ and we are done. If $xy \in M$, then $y \ne u_1, u_2$ (they are matched to each other) and $y \ne u_0$ (unmatched), so $y \notin S$: the edge $xy \in M_S$ leaves $S$. Done.

In Cases B-D we have $\deg(u_2) = 1$, i.e. $u_2$ is a leaf whose unique neighbor is $u_1$.

Case B: some neighbor $z \notin \{u_0, u_2\}$ of $u_1$ is matched, say $zz' \in M$. Then $z' \ne u_1, u_2$ ($M$ is a matching and $u_1u_2 \in M$), $z' \ne u_0$ (unmatched), $z' \ne z$. So $P = (u_0, u_1, z, z')$ is a path on $4$ distinct vertices. Here $M_S = \{u_1u_2,\ zz'\}$ ($u_0$ is unmatched; $u_1$ is covered only by $u_1u_2$; $z, z'$ only by $zz'$), and $u_1u_2$ has the endpoint $u_2 \notin S$ (indeed $u_2 \notin \{u_0, u_1, z, z'\}$). Done.

Case C: every neighbor of $u_1$ outside $\{u_0, u_2\}$ is unmatched, and $\deg(u_0) \ge 2$. Pick a neighbor $w \ne u_1$ of $u_0$; then $w \ne u_2$ ($u_2$ is a leaf adjacent only to $u_1$). The vertex $w$ must be matched, else $M \cup \{u_0w\}$ is larger; say $ww' \in M$. Then $w' \ne u_0$ (unmatched), $w' \ne u_1, u_2$ (matched to each other), $w' \ne w$. So $P = (w', w, u_0, u_1)$ is a path on $4$ distinct vertices, $M_S = \{ww',\ u_1u_2\}$, and $u_1u_2$ has the endpoint $u_2 \notin S$. Done.

Case D: every neighbor of $u_1$ outside $\{u_0, u_2\}$ is unmatched and $\deg(u_0) = 1$ (so $u_0$ and $u_2$ are both leaves attached to $u_1$). If every vertex other than $u_1$ were adjacent to $u_1$, then $T$ would be a star centered at $u_1$ --- excluded above. Hence some vertex lies at distance $\ge 2$ from $u_1$: there exist $z$ adjacent to $u_1$ and $z'$ adjacent to $z$ with $z' \ne u_1$. Since $u_0, u_2$ are leaves adjacent only to $u_1$, we get $z \notin \{u_0, u_2\}$ and $z' \notin \{u_0, u_2\}$. By the case hypothesis $z$ is unmatched; then $z'$ must be matched (else $M \cup \{zz'\}$ is larger), say $z'z'' \in M$. Then $z'' \ne z$ ($z$ unmatched), $z'' \ne u_0$ (unmatched), and $z'' \ne u_1, u_2$ (they are covered by the different matching edge $u_1u_2$, and $z'z'' \ne u_1u_2$ because $z' \notin \{u_1, u_2\}$). So $P = (u_1, z, z', z'')$ is a path on $4$ distinct vertices, $M_S = \{u_1u_2,\ z'z''\}$ ($z$ is unmatched), and $u_1u_2$ has the endpoint $u_2 \notin S$. Done.

Cases A-D exhaust all possibilities. $\blacksquare$

\textbf{LEMMA 3 (a good move under a perfect matching).} If $T$ has a perfect matching $M$ and $n \ge 4$, then some operation produces $T'$ with $\mu(T') \ge \mu(T) - 2$.

Proof. Take any leaf $u_0$ with unique neighbor $u_1$; since $M$ is perfect and $u_0$ has only one edge, $u_0u_1 \in M$. If $\deg(u_1) = 1$ then $T = K_2$, contradicting $n \ge 4$; so $u_1$ has a neighbor $u_2 \ne u_0$. Since $M$ is perfect, $u_2u_3 \in M$ for some $u_3$; moreover $u_3 \ne u_1$ ($u_1$ is matched to $u_0$) and $u_3 \ne u_0$. Hence $P = (u_0, u_1, u_2, u_3)$ is a path on $4$ distinct vertices and $M_S = \{u_0u_1,\ u_2u_3\}$. Lemma S gives $\mu(T') \ge \mu - 2$. $\blacksquare$

\textbf{THEOREM.} For every tree $T$ on $n \ge 2$ vertices, the maximum possible number of operations equals

$$
f(T) = \min\left(\left\lfloor \frac{n-1}{3}\right\rfloor,\ \mu(T) - 1\right),
$$

and therefore the minimum reachable size is $n - 3 f(T)$. (For $n = 1$, trivially $f = 0$ and the answer is $1$.)

Proof. The inequality $f(T) \le \min(\cdot,\cdot)$ is the Corollary. We prove $f(T) \ge \min(\cdot,\cdot)$ by strong induction on $n$. Write $m = \lfloor (n-1)/3 \rfloor$ and $t = \min(m, \mu - 1)$.

If $t = 0$ there is nothing to prove. So assume $t \ge 1$; then $n \ge 4$ and $\mu \ge 2$.

Case (i): $T$ has no perfect matching. First, $n \ge 5$: the only trees on $4$ vertices are $P_4$ and $K_{1,3}$; $K_{1,3}$ has $\mu = 1 < 2$, and $P_4$ has a perfect matching. Apply Lemma 2 and perform that operation: the resulting tree $T'$ has $n' = n - 3 \ge 2$ vertices and $\mu(T') \ge \mu - 1$. Using $\lfloor (n-4)/3 \rfloor = m - 1$ and the induction hypothesis,

$$
f(T') \ge \min\big(\lfloor (n'-1)/3 \rfloor,\ \mu(T') - 1\big) \ge \min(m - 1,\ \mu - 2) = t - 1,
$$

hence $f(T) \ge 1 + f(T') \ge t$.

Case (ii): $T$ has a perfect matching, so $n = 2\mu$. Then $m \le \mu - 1$, because $\lfloor (2\mu - 1)/3 \rfloor \le \mu - 1 \iff (2\mu - 1)/3 < \mu \iff \mu > -1$, which always holds. Hence $t = m$.

If $\mu = 2$: the only tree on $4$ vertices with a perfect matching is $P_4$ (the other one, $K_{1,3}$, has none). One operation contracts it entirely, so $f(T) \ge 1 = m = t$.

If $\mu \ge 3$: apply Lemma 3, obtaining $T'$ with $n' = 2\mu - 3 \ge 3$ vertices and $\mu(T') \ge \mu - 2$. We claim $\mu - 2 \ge m$: since $m$ is an integer, $m \le \mu - 2 \iff (2\mu - 1)/3 < \mu - 1 \iff 2\mu - 1 < 3\mu - 3 \iff \mu > 2$, true. Also $\lfloor (n'-1)/3 \rfloor = \lfloor (n-4)/3 \rfloor = m - 1$. By the induction hypothesis,

$$
f(T') \ge \min\big(m - 1,\ \mu(T') - 1\big) \ge \min(m - 1,\ m - 1) = m - 1,
$$

hence $f(T) \ge 1 + (m - 1) = m = t$. $\blacksquare$

</spoiler>