Return to Answer

I discussed this problem with Ringi Kim and Paul Seymour.

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.)

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 in $T'$.)

1. There is another center in $T'$.

Suppose $u$ is the unique center in $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 in $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 in $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$$

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

$u$ is still a center in $T''$ as it was in $T'$. But, $v$ is not a center in $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 in $T''$. And if there is one, then it must be in $T_u$ since $v$ is not a center in $T''$.

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 in $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 in $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|$.

Suppose $u$ is the unique center in $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 in $T'$. This means that $d_{T'}(u) = d_T(u)$ and $v$ is still a center as well. This proves (1).

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 in $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$.

For the sake of contradiction, suppose $u$ is another center in $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).

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$$

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''$.

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|$.

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).

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$.

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).

Therefore no vertex has degree 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.

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

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.

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