Does this poset have a unique minimal element? - MathOverflow

Does this poset have a unique minimal element?

2012-12-24T16:35:44Z

Recently I have been thinking about the following poset: the underlying set is $\mathcal{AFT}$ consisting of all (finite) automorphism-free undirected trees (with at least one edge to exclude the trivial cases pointed out by Joel) and the poset relation $\leq$ is defined by $T \leq U$ if $T$ can be obtained from $U$ by successively deleting one leaf node at a time in such a way that each intermediate tree is also an element of $\mathcal{AFT}$.

The smallest element of $\mathcal{AFT}$ is the seven node tree which is the Dynkin diagram of $E_7$ (and which I will therefore refer to simply as $E_7$ from herein):

So $E_7$ is certainly a minimal element in the above partial order.

Question: Does $(\mathcal{AFT},\leq)$ have a unique minimal element, namely $E_7$?

There are several equivalent formulations of this question which I have considered, hoping one of them might lead somewhere useful:

Question 2: Can every element of $\mathcal{AFT}$ be obtained by starting at $E_7$ and successively adjoining leaf nodes so that we remain in $\mathcal{AFT}$ at every stage?

Question 3: Is there an element of $\mathcal{AFT}$ besides $E_7$ such that deleting $any$ single leaf node results in a tree not in $\mathcal{AFT}$.

Question 3 in particular seems simple enough that it must have been answered somewhere before, but alas almost any search for 'automorphism-free' and 'trees' results in papers about the result that almost every tree has an automorphism or results on the fixed vertices/edges of trees under automorphisms.

Trying to construct a minimal example larger than $E_7$ for Question 3 keeps leading to near-misses where all but one leaf nodes' removal takes us outside $\mathcal{AFT}$, but after removing this one leaf node, there is still a sequence of removals remaining in $\mathcal{AFT}$ that leads back to $E_7$ which is the best evidence I have so far that Question 1 is true.

So, does anyone know where this might have been considered already, and if so, if the answer to Question 1 is affirmative?

Answer by Pietro Majer for Does this poset have a unique minimal element?

2012-12-25T18:15:28Z

[edit 01.15.2013] The following proof is still incomplete, but the main ideas should be useful.

[edit 01.17.2013] I filled the lacking point in the case 2, small but subtle, completing the proof, so I wrote it (even if in the meanwhile a complete proof has been posted).

Let me start with some general notions, that I believe are known, for a tree $T=(V,E)$ with finite, nonempty vertex set $V$ and edge set $E$. I will assume that $T$ is a minimal element of $\mathcal{AFT}$ only in the end.

For a path of length $n$ (number of edges) , $ (v_0 \dots v_n) $ in $ T $, let's define the centre of the path as the set $ \big\{v _ {\lfloor\frac{n }{2}\rfloor},v _ {\lceil \frac{n }{2}\rceil } \big\}$, consisting of one or two vertices (thus, either the middle vertex, if $n$ is even, or the middle edge, if $n$ is odd). Given two paths, there is a third path including the centres of both, and one endpoint of each. As a consequence, all paths of maximum length in a tree share the same centre, that we can therefore refer to as centre of the tree, $C(T):=\{v,v'\}$ (so this notation allows that $C(T)=\{v\}=\{v'\}$, a singleton, precisely whenever the diameter of $T$ is an even number, as remarked).

Since the image of a maximum length path via an automorphism of $T$ is still a maximum length path, whose center is the image of the center of the path, the set $C(T)$ is invariant for any automorphism $f$ of $T$ (thus, it is either a fixed point, or a couple of fixed points , or a 2-periodic orbit of $f$).

The centre determines a natural genealogy order in $T$; in particular, we can attach to any vertex $v$ its progeny, $\Gamma(v,T)$, the set of all vertices $x$ such that the minimal path from $x$ to the centre passes by $v$. Thus, e.g. this reduces to $\{v\}$ if and only is $v$ is a leaf; if $ C(T)$ is a singleton $\{v\}$, $\Gamma(v,T)$ is the whole vertex set $V$; if $ C(T)$ is an edge $vv'$, $\Gamma(v,T)$ and $\Gamma(v',T)$ are the components of $(V, E\setminus\{C(T)\}$.

For a vertex $x$, denote $( x^0 \dots x^n )$ the unique minimal path in $ T $ connecting $x$ to the center: $x^0\in C(T)$, $x^n=x$; here $n$ is the path distance from $C(T)$. It is also convenient to consider the nested sequence $ \Gamma(x^i,T) $, and the vector $\gamma(x,T):=(\gamma_0,\dots,\gamma_n)\in\mathbb{N}^{n+1}$ whose $i$-th entry is the cardinality $\gamma_i:=|\Gamma (x^i,T)|$ of each of these sets. Note that, since the center of a tree is automorphism-invariant, any automorphism of $T$ satisfy $\gamma(f(x),T)=\gamma(x,T)$. Among all leaves, consider those with minimum $\gamma(x,T)$ in the lexicographic order (with leading coefficient $\gamma_0$ ); we may shortly call them minimal leaves. For instance, the three leaves of the tree $E_7$ have labels $(3,2,1)$, $(4,1)$, and $(4,3,1)$, in increasing lexicographic order.

Let $x$ be a leaf of $T$, with father $x'=x^{n-1}$. We may denote $ T_x:=(V_x,E_x)$ the tree obtained deleting the leaf $x$ and the edge $xx'$. For a minimal leaf $x$ we may distinguish the following alternative:

1. $\mathrm{diam}(T_x)=\mathrm{diam}(T)$. This means that $T$ and $T_x$ share a maximum length path, so they also have the same center. Thus, for any $v\in V_x$ we have $\Gamma(v,T_x)=\Gamma(v,T)\setminus\{x\}$, and in particular the entries of $\gamma(x',T_x)$ are simply $\gamma_i(x',T_x) = \gamma_i(x,T) -1$ for $i=0,\dots,n-1$. As a consequence, any automorphism $f$ of $T_x$ fixes the whole path connecting $x'$ to $C(T_x)=C(T)$ (this follows by induction on $i$, arguing on the cardinality of the connected components $\Gamma (x^i,T_x)$: now $\Gamma (x^0,T_x)$ has strictly minimum cardinality among the components of $(V_x, E_x\setminus \{C(T)\})$, so $f(\Gamma (x^0,T_x))=\Gamma(x^0,T_x)$ and $x^0$ is fixed; then $x^1$ is fixed because $\Gamma(x^1,T_x)$ has strictly minimum cardinality among the components of the sons of $x^0$ in $\Gamma (x^0,T_x)$, and so on ). Therefore, $f$ extends to an automorphism of $T$ that fixes $x$. Clearly, this is not the case if $T$ is a minimal element of $\mathcal{AFT}$.

2. $\mathrm{diam}(T_x)=\mathrm{diam}(T)-1$. This means that $x$ is an end of every maximal length path of $T$.

Now, assume $T$ is a minimal element in $\mathcal{AFT}$, so that we are in case 2. Then, $C(T)$ is an edge, i.e. $\mathrm{diam}(T)$ is an odd number $2n+1$, and no vertex of the minimal path $(x^0,\dots, x^{n})$ connecting $x$ to $C(T)$ is a branching point. Proof: consider first the case of odd diameter of $T$, where $C(T)$ is an edge. Assume by contradiction that $\Gamma(x^0, T)$ is not a single path. Then, there are in it leaves $y\neq x$. Take among them the one with minimum vector $\gamma(y,T)$ in the lexicographic order. Now, since $y\neq x$, we have $\mathrm{diam}(T_y)=\mathrm{diam}(T)$, and we can argue with $y$ like in the previous case 1. The automorphism $f_y$ of $T_y$ fixes all $x^i$ because $( f_y(x^0),\dots,f_y(x^n) )$ are an end of a maximum lenght path in $T$, so they must end at $x$, which implies $f_y(x^i)=x^i$ for $0\le i \le n$. But then, $f_y$ also fixes the path $y^i$, for the same inductive argument used in point $1$ (start with the greater index $j$ such that $x^j=y^j$ and proceed looking at the cardinality of $\Gamma(y^{j+1} , T_y)$, observing that $f_ y (y ^ {j+1} ) \neq x^{j+1} =f_y(x^{j+1} ) $ because $ y^{j+1} \neq x^{i+1}$. This is a contradiction as usual, because $f_y$ does not fix the father of $y$, as already observed. For an analog reason, the case $C(T)$ is a vertex implies that $\Gamma(x,T)$, that is the whole $T$, has no branching vertices, that is, it is a path, which however is impossible because $T$ has no nontrivial automorphism.

Conclusion of the proof: Since $(x^0,\dots, x^{n-1})$ is part of a maximum length path in $T_x$, and $ \mathrm{diam}(T_x)=2n $ is even, the center of $T_x$ is a single vertex, namely the other endpoint $y^0$ of $C(T):=\{x^0,y^0\}$. If $f_x$ denote the unique nontrivial automorphism of $T_x$, we know that $f_x(y_0)=y_0$ (it's the center of $T_x$), while $y:=f_x(x^{n-1})\neq x^{n-1} $ (otherwise $f_x$ would extend to $T$). Therefore, $ (y^0, f_x(x^0),f_x(x^1),\dots,f_x(x^{n-1}))$ is the $n$-edges path connecting $y$ to $C(T)$, and since the $x^i$ for $i\ge0$ are not branching points, this path has no branching points too, with the possible exception of $y^0$. Actually, $y^0$ must be a branching point, otherwise the path $\xi:=(x^n,x^{n-1},\dots,x^0,y^0,y^1,\dots y^n)$, which has maximal length $2n+1$ in $T$, would have no branching point at all, and therefore would be $T$ itself, what however is impossible because $T$ has no nontrivial automorphism.

Next, we may consider the automorphism $f_y$ of $T_y$. As to $C(T_y)$, it is either $\{x^0\}$ (if $\xi$ is the unique maximum length path of $T$ and $ \mathrm{diam}(T_y)=2n $) , or $C(T_y)=C(T)$, (if there are other maximum length paths in $T$ and $ \mathrm{diam}(T_y)=2n+1 $). Therefore $f_y(y_0)$ is either $x^0$, or $x^1$, or $y^0$; however, only the last case is possible, because $y_0$ is a branching points and $x^0$, or $x^1$ are not. Thus, $( f_y(y^0), f_y(y^1),\dots, f_ y(y^{n-1}))$ is a path of length $n-1$ , starting from the branching point $y^0=f_ y(y^0)$, without other branching points. For the same reason, $T$ must contain a family of paths emanating from $y^0$, with no branching points, of all lengths between $1$ and $n$; in particular, a leaf $z$ attached to $y^0$ (and possibly other matter). The unique involution $f$ of $T_z$ exchanges the endpoints of $C(T_z)=C(T)$ (otherwise it would be extensible to a nontrivial automorphism of $T$), therefore bijects the whole $\Gamma(x^0, T)=\Gamma(x^0, T_z)$ with $\Gamma(y^0, T_z)$. This proves that $n=2$ and $T$ is $E_7$.

Answer by Ilhee Kim for Does this poset have a unique minimal element?

2013-01-14T21:43:48Z

The answer is yes. With Ringi Kim and Paul Seymour, we proved this a few days ago, and the following is the proof. (I am not sure if this is already known or not. Please let me know if it is.)

Some definitions first. For a tree $T$ and $u,v \in V(T)$, $dist_T(u,v)$ is the length of the (unique) path from $u$ to $v$ in $T$. $T \setminus u$ denotes the forest obtained from $T$ by deleting the vertex $u$ (deleting all the edges incident to $u$ as well). $T \setminus uv$ denotes the forest obtained from $T$ by deleting the edge $uv$ (not deleting the vertices $u$ and $v$). For each $v \in V(T)$, $d_T(v) := \max_{u \in V(T) \setminus {v}} dist_T(u,v)$. We say $v \in V(T)$ is a center of $T$ if $d_T(v)$ attains its minimum over all vertices. The following are some easy facts about centers in a tree.

1) There are at most 2 centers in a tree.

2) If there are 2 centers $u$ and $v$, then $uv \in E(T)$. Moreover, every path of length $d_T(u)$ from $u$ passes $v$ and vise versa.

Now, here is our strategy. We are going to look at a minimal tree $T$ in the poset AFT. And we will choose special leaves $l_1$ and $l_2$ by certain methods, and use the fact that both $T \setminus l_1$ and $T \setminus l_2$ are not in AFT. From this, we will prove various properties of $T$. For instance, we will prove that $T$ must have two centers, and $T \setminus l_1$ must have exactly one center, and $T \setminus l_2$ must have two centers, etc. Eventually we will prove that $T$ must be isomorphic to $E_7$.

We first introduce the method of choosing a special leaf. Let $T$ be a tree with $|V(T)| \geq 2$, and let $u$ be a vertex in $T$. We are going to pick a leaf with respect to $u$ and $T$ as follows.

Consider all neighbors of $u$. Each one is in its own component $C_1,\cdots,C_k$ of $T \setminus u$. Among those components, we take one with the least number of vertices. (If there are more than one smallest components, just pick any one of those.) Let $C_1$ be the component we chose and let $w$ be the neighbor of $u$ in $C_1$. Now, look at all children of $w$ (the neighbors of $w$ except $u$). If there are no children of $w$, then we take $w$ as our special leaf. Otherwise we consider components $D_1,\cdots,D_m$ of $C_1 \setminus w$ and again, we pick the smallest component, and we move one step ahead. By this algorithm, we will end up with a leaf and we will take that leaf as our special leaf with respect to $u$ and $T$.

Theorem 1. Let $T$ be a minimal tree in the poset AFT. Then $T$ has exactly two centers.

Proof. For the sake of contradiction, suppose $T$ has a unique center $u$. Let $l_1$ be the special leaf with respect to $u$ and $T$ as described above.

Now, consider the tree $T' = T \setminus l_1$. In $T'$, $u$ is still a center because $d_{T'}(v)$ is either $d_{T}(v)$ or $d_{T}(v) - 1$ for every $v \in V(T) \setminus l_1$, and $d_T(u)$ used to be the unique minimum in $T$. (But there might be another center of $T'$.)

1) There is another center of $T'$.

Suppose $u$ is the unique center of $T'$. Let $\phi$ be a non-trivial automorphism in $T'$. Let $p(l_1)$ be the parent (the unique neighbor) of $l_1$ in $T$. Notice that $\phi$ does not fix $p(l_1)$ because otherwise we can extend $\phi$ to $T$ by assigning $\phi(l_1) = l_1$. On the other hand, $\phi$ fixes $u$ since it is the unique center of $T'$. Let $P$ be the path from $u$ to $p(l_1)$ in $T'$. Then, it is clear that $\phi$ fixes a sub-path $P'$ of $P$ containing $u$, and $\phi$ does not fix the other part of the path containing $p(l_1)$. Let $u'$ be the last vertex of $P'$. ($u'$ might be equal to $u$.) Then, $T' \setminus u'$ has (at least) two components which are isomorphic. And one of them must contain $p(l_1)$ since otherwise we can extend $\phi$ to $T$. Let $C_1$ and $C_2$ be those isomorphic components in $T' \setminus u'$ and say $p(l_1) \in C_1$. In particular $|C_1| = |C_2|$. But in $T$, $C_1 \cup l_1$ and $C_2$ are two components of $T \setminus u'$ and $|C_1 \cup l_1| > |C_2|$. This is a contradiction to our choice of $l_1$. This proves (1).

Let $v$ be the other center of $T'$. $u$ used to be the unique center of $T$, but now $u$ and $v$ are two centers in $T \setminus l_1$. Therefore it must be the case that $$d_{T'}(u) = d_T(u) = d_{T'}(v) = d_T(v) - 1$$

2) $l_1$ is not a neighbor of $u$.

Suppose $l_1$ is a child of $u$. Then, $d_{T'}(v) = d_T(v) - 1 = dist_T(v, l_1) - 1 = 1$. Therefore $T'$ has exactly two vertices $u$ and $v$. This is a contradiction to the fact that $T$ is in AFT. This proves (2).

3) $v$ is not in the component $C_1 \setminus l_1$ of $T' \setminus u$.

The path from $v$ to $l_1$ is the unique path of length $d_T(v)$ starting from $v$ in $T$. In particular, the path from $v$ to $p(l_1)$ is a path of length $d_T(v)-1 = d_{T'}(v)$. Recall that $u$ and $v$ are adjacent. Therefore if $v$ is in $C_1 \setminus l_1$, then the path from $v$ to $p(l_1)$ does not pass $u$. A contradiction. This proves (3).

4) $p(l_1)$ is a leaf in $T'$.

Suppose $p(l_1)$ has a child $w$ other than $l_1$ in $T$. Then, the path from $v$ to $w$ in $T'$ has length $d_{T'}(v)+1$ and this contradicts the definition of $d_{T'}$. This proves (4).

5) $\phi$ switches $u$ and $v$.

Notice that either $\phi$ fixes $u$ and $v$ or switches them since they are centers. But if $\phi$ fixes $u$, then by the same argument as in (1), we get a contradiction to our choice of $l_1$. This proves (5).

Let $T_u$ and $T_v$ be the two components of $T' \setminus uv$. ($T_u$ contains $u$ and $T_v$ contains $v$.) Since $\phi$ switches $u$ and $v$, $T_u$ and $T_v$ must be isomorphic. Note that $\phi$ does not fix any vertex. Recall that $p(l_1)$ is a leaf in $T_u$ from (4). Therefore $\phi(p(l_1))$ is also a leaf in $T_v$. Clearly it is a leaf in $T$ as well. Let $l_2 = \phi(p(l_1))$. (It is easy to see that this $l_2$ is actually the special leaf with respect to $v$ and $T$.)

We now consider $T'' = T \setminus l_2$.

6) $u$ is still a center of $T''$, but $v$ is not.

$u$ is still a center of $T''$ as it was in $T'$. But, $v$ is not a center of $T''$ since $d_{T''}(v) = dist_{T''}(v,l_1) = d_{T}(v) > d_{T}(u) \geq d_{T''}(u)$. This proves (6).

Again, there might be another center of $T''$. And if there is one, then it must be in $T_u$ since $v$ is not a center of $T''$.

Now consider a non-trivial automorphism $\phi'$ of $T''$.

7) $\phi'$ does not fix $v$.

For the sake of contradiction, suppose $\phi'$ fixes $v$. Then $u$ is fixed as well because $u$ is the unique center among the neighbors of $v$ (although $u$ might not be the unique center of $T''$.) By the similar argument as before, the parent of $l_2$ is not fixed by $\phi'$ and this yields a contradiction to the fact that $l_2$ is a special leaf with respect to $v$. This proves (7).

Clearly, $\phi'(v)$ is in $T_u$ since it is adjacent to a center of $T''$ and not equal to $v$. Then, there must be some component $C$ of $T'' \setminus u$ either isomorphic to $T_v \setminus l_2$ or contains it. In any case, $C$ has size at least $|T_v \setminus l_2|$. Let $n = |T_v|$.

8) $|C| = n$ or $n-1$.

$|C| \geq n-1$ since $\phi'(V(T_v) \setminus l_2) \subseteq C$. Recall that $|T_u| = |T_v|$ and $C$ is a subset of $V(T_u) \cup {l_1} \setminus {u}$. Therefore $|C| \leq |V(T_u) \cup {l_1} \setminus {u}| = n + 1 - 1 = n$. This proves (8).

9) The degree of $u$ is 2. In particular, $T''\setminus u$ consists of two isomorphic components, namely $C$ and $T_v \setminus l_2$.

Note that the union of all components of $T''\setminus u$ other than $T_v\setminus l_2$ has size $|V(T_u) \cup {l_1} \setminus {u}| = n$. Therefore if there is another component of $T'' \setminus u$ other than $C$ and $T_v\setminus l_2$, then it must be a single vertex. Therefore $u$ has degree either 2 or 3. If $u$ has degree 3, then it has a neighbor who has degree 1. Then this leaf must have been our choice $l_1$. But by (2), this is impossible. Therefore $u$ has exactly two neighbors. This proves (9).

Suppose there are some vertices of degree at least 3 in $C$. Now let $x$ be the shortest distance from $u$ to a vertex of degree at least 3 in $C$. And let $y$ be the shortest distance from $v$ to a vertex of degree at least 3 in $T_v$. Since $T_u$ and $T_v$ are isomorphic, $x = y$.

On the other hand, the shortest distance from $u$ to a vertex of degree at least 3 in $T_v$ is $y + 1$. Since $T_v \setminus l_2$ is isomorphic to $C$, the shortest distance from $u$ to a vertex of degree at least 3 in $C$ is $y+1$. Therefore $x = y+1$ and this is a contradiction.

Therefore no vertex has degree at least 3 in $C$. And this implies that $T$ is a path. And this is a contradiction to the fact that $T$ is in AFT. This proves Theorem 1.

Theorem 2. Let $T$ be a minimal tree in the poset AFT. Then $T$ is isomorphic to $E_7$

Proof. From Theorem 1, $T$ has two centers $u$ and $v$. Let $T_u$ and $T_v$ be the two sub-trees in $T \setminus uv$. ($T_u$ contains $u$ and $T_v$ contains $v$.)

Let $l_1$ be the special leaf with respect to $u$ and $T_u$ and let $l_2$ be the special leaf with respect to $v$ and $T_v$. Let $x$ be the shortest distance from $u$ to a vertex of degree at least 3 in $T_u$. (If there aren't any vertices of degree 3 in $T_u$, then $T_u$ is a path, and set this number $x$ as the length of the path.) Similarly, let $y$ be the shortest distance from $v$ to a vertex of degree at least 3 in $T_v$.

Without loss of generality, we may assume $|T_u| \leq |T_v|$. And further we may assume if $|T_u| = |T_v|$ then $x \leq y$ by switching $u$ and $v$ if necessary.

We first look at $T' = T \setminus l_2$.

1) $u$ and $v$ are still two centers of $T'$.

Note that every path of length $d_T(v)$ starting from $v$ passes $u$ in $T$. Therefore this path still exists in $T'$ since $l_2 \in T_v$. Therefore $d_{T'}(v) = d_T(v)$. This means that $u$ is still a center of $T'$.

Suppose $u$ is the unique center of $T'$. Let $\phi$ be a non-trivial automorphism of $T'$. Then, $\phi$ does not fix $v$ since otherwise we get a contradiction to our choice of $l_2$.

Then the component $T_v \setminus l_2$ of $T' \setminus u$ is isomorphic to some other component $C$ of $T' \setminus u$. Note that $$|C| = |T_v \setminus l_2| = |T_v| - 1$$ Since $C$ is a subset of $V(T_u) \setminus {u}$, $$|T_u| \geq |C| + 1 = |T_v|$$ Therefore $|T_u| = |T_v|$. And $T' \setminus u$ has exactly two components, namely $C$ and $T_v \setminus l_2$. We may assume there is a vertex of degree at least 3 in $T_v \setminus l_2$, since otherwise $T$ is a path. But then, $x \geq y+1$ and this is a contradiction to our assumption ($x \leq y$ if $|T_u| = |T_v|$). Therefore $u$ is not the unique center of $T'$. This means that $d_{T'}(u) = d_T(u)$ and $v$ is still a center as well. This proves (1).

2) $\phi$ switches $u$ and $v$. And $|T_u| = |T_v| -1$.

Again, if $\phi$ fixes $v$, then $\phi$ fixes $u$ as well and we get a contradiction to our choice of $l_2$. Since $\phi$ switches $u$ and $v$, $T_u$ and $T_v \setminus l_2$ are isomorphic. In particular, $|T_u| = |T_v| - 1$. This proves (2).

Now we consider $T'' = T \setminus l_1$. Let $\phi'$ be a non-trivial automorphism of $T''$.

3) $\phi'$ does not fix $u$. And $v$ is the unique center of $T''$.

Again, every path of length $d_T(u)$ starting from $u$ passes $v$ in $T$. Therefore this path still exists in $T''$ since $l_1 \in T_u$. Therefore $d_{T'}(u) = d_T(u)$. This means that $v$ is still a center of $T''$.

Note that either $d_{T'}(v) = d_T(v)-1$ or $d_{T'}(v) = d_T(v)$. In the former case, $v$ is the unique center of $T''$, and in the latter case, $u$ and $v$ are again two centers of $T''$. Therefore if there is another center, then it must be $u$.

Suppose $\phi'$ fixes $u$. Then, again $v$ is fixed as well and we get a contradiction to the choice of $l_1$. Therefore $\phi'$ does not fix $u$.

For the sake of contradiction, suppose $u$ is another center of $T''$. Since $\phi'$ does not fix $u$, it switches $u$ and $v$. Then, $T_u \setminus l_1$ is isomorphic to $T_v$, but $|T_u \setminus l_1| = |T_u| - 1 = |T_v| - 2 \neq |T_v|$. A contradiction. This proves (3).

Since $v$ is the unique center of $T''$ and $\phi'$ does not fix $u$, the component $T_u \setminus l_1$ of $T'' \setminus v$ is isomorphic to another component $C$ of $T'' \setminus v$.

Note that the union of all components of $T''\setminus v$ other than $T_u \setminus l_1$ is exactly $T_v \setminus v$. And $C$ has size $|T_u| - 1 = |T_v| - 2$. This means that there are exactly three components of $T''\setminus v$, namely $T_u \setminus l_1$, $C$, and the third one with a single vertex. Therefore $v$ has a neighbor of degree 1, and this must have been our choice $l_2$.

Now suppose there is a vertex of degree at least 3 in $T_u$. Then there is one in $T_v$ as well. And by the usual argument, $x=y$ and $x+1 = y$ at the same time. A contradiction. Therefore $T_u$ must be a path of length $|T_u|$ and $T_v$ must be a path of length $|T_v| = |T_u| + 1$.

Then, $T$ is a tree with a unique vertex of degree 3, namely $v$, and $T \setminus v$ has three components. One of them is a single vertex, namely $l_2$, and the other two components are paths of length $k$ and $k+1$.

For every $k > 2$, $T$ is not minimal since deleting $l_1$ from $T$ yields a smaller tree $T''$ in AFT. Therefore $k$ must be 2. This proves that $T$ must be isomorphic to $E_7$.