Does this poset have a unique minimal element? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T13:27:19Z http://mathoverflow.net/feeds/question/117151 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/117151/does-this-poset-have-a-unique-minimal-element Does this poset have a unique minimal element? ARupinski 2012-12-24T16:35:44Z 2013-01-17T22:47:52Z <p>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}$.</p> <p>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):</p> <p><IMG SRC="http://upload.wikimedia.org/wikipedia/commons/a/a3/Dynkin_diagram_E7_%28no_numbers%29.png"></p> <p>So $E_7$ is certainly a minimal element in the above partial order.</p> <blockquote> <blockquote> <p><b>Question:</b> Does $(\mathcal{AFT},\leq)$ have a unique minimal element, namely $E_7$?</p> </blockquote> </blockquote> <p>There are several equivalent formulations of this question which I have considered, hoping one of them might lead somewhere useful:</p> <blockquote> <blockquote> <p><b>Question 2:</b> 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?</p> </blockquote> </blockquote> <p>></p> <blockquote> <blockquote> <p><b>Question 3:</b> 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}$.</p> </blockquote> </blockquote> <p>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.</p> <p>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.</p> <p>So, does anyone know where this might have been considered already, and if so, if the answer to Question 1 is affirmative?</p> http://mathoverflow.net/questions/117151/does-this-poset-have-a-unique-minimal-element/117206#117206 Answer by Pietro Majer for Does this poset have a unique minimal element? Pietro Majer 2012-12-25T18:15:28Z 2013-01-17T22:47:52Z <p><em>[edit 01.15.2013] The following proof is still incomplete, but the main ideas should be useful.</em></p> <p><em>[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).</em></p> <p>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.</p> <p>For a path of length $n$ (number of edges) , $(v_0 \dots v_n)$ in $T$, let's define the <em>centre</em> 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 <em>centre of the tree</em>, $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).</p> <p>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$).</p> <p>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)\}$.</p> <p>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 <em>minimal leaves</em>. 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.</p> <p>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:</p> <p><strong>1.</strong> $\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 <em>strictly</em> 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}$. </p> <p><strong>2.</strong> $\mathrm{diam}(T_x)=\mathrm{diam}(T)-1$. This means that $x$ is an end of every maximal length path of $T$. </p> <p>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. </p> <p>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$ <em>must</em> 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. </p> <p>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$. </p> http://mathoverflow.net/questions/117151/does-this-poset-have-a-unique-minimal-element/118925#118925 Answer by Ilhee Kim for Does this poset have a unique minimal element? Ilhee Kim 2013-01-14T21:43:48Z 2013-01-16T19:35:52Z <p>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.)</p> <p>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.</p> <p>1) There are at most 2 centers in a tree.</p> <p>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.</p> <p>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$.</p> <p>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.</p> <p>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$.</p> <p>Theorem 1. Let $T$ be a minimal tree in the poset AFT. Then $T$ has exactly two centers.</p> <p>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.</p> <p>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'$.)</p> <p>1) There is another center of $T'$.</p> <p>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).</p> <p>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$$</p> <p>2) $l_1$ is not a neighbor of $u$.</p> <p>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).</p> <p>3) $v$ is not in the component $C_1 \setminus l_1$ of $T' \setminus u$.</p> <p>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).</p> <p>4) $p(l_1)$ is a leaf in $T'$.</p> <p>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).</p> <p>5) $\phi$ switches $u$ and $v$.</p> <p>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).</p> <p>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$.)</p> <p>We now consider $T'' = T \setminus l_2$.</p> <p>6) $u$ is still a center of $T''$, but $v$ is not.</p> <p>$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).</p> <p>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''$.</p> <p>Now consider a non-trivial automorphism $\phi'$ of $T''$.</p> <p>7) $\phi'$ does not fix $v$.</p> <p>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).</p> <p>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|$.</p> <p>8) $|C| = n$ or $n-1$.</p> <p>$|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).</p> <p>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$.</p> <p>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).</p> <p>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$.</p> <p>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.</p> <p>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.</p> <p>Theorem 2. Let $T$ be a minimal tree in the poset AFT. Then $T$ is isomorphic to $E_7$</p> <p>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$.)</p> <p>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$.</p> <p>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.</p> <p>We first look at $T' = T \setminus l_2$.</p> <p>1) $u$ and $v$ are still two centers of $T'$.</p> <p>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'$.</p> <p>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$.</p> <p>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).</p> <p>2) $\phi$ switches $u$ and $v$. And $|T_u| = |T_v| -1$.</p> <p>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).</p> <p>Now we consider $T'' = T \setminus l_1$. Let $\phi'$ be a non-trivial automorphism of $T''$.</p> <p>3) $\phi'$ does not fix $u$. And $v$ is the unique center of $T''$.</p> <p>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''$.</p> <p>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$.</p> <p>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$.</p> <p>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).</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> <p>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$.</p> <p>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$.</p>