A distance between isomorphism classes of trees

NEW

Problem: Zelinka’s Conjecture 1 is reconstructed as follows. For $n$-vertex trees $T,T'$, let

where $m(T,T')$ is the maximum order of a tree isomorphic to a connected subtree of both $T$ and $T'$. Let $\mathscr G_n$ be the graph whose vertices are isomorphism classes of $n$-vertex trees, with two classes adjacent when $\rho=1$; its graph metric equals $\rho$. For a tree $T$, write $\Delta(T)$ for maximum degree and $D(T)$ for diameter, and let

The conjecture says

Result: The conjecture is false. A counterexample occurs at $n=13$.

First, $\sigma(13)=7$. Indeed every $13$-vertex tree satisfies

so $\min\{\Delta,D\}\le 7$. Equality is attained by taking a path of length $7$ and attaching five extra leaves to an internal path vertex, giving $\Delta=D=7$. Thus the conjectured radius is

Suppose some $13$-vertex tree $T$ had eccentricity at most $5$. Let $S=K_{1,12}$ and $P=P_{13}$. Since

we must have $\Delta(T)\ge 7$ and $D(T)\ge 7$. Hence $\Delta(T)=D(T)=7$. The equality case in $\Delta+D\le 14$ forces $T$ to be a path of length $7$ with five additional leaves attached to one internal path vertex. Up to symmetry, there are only three such trees.

Now define a $13$-vertex tree $W$ with edges

Every $8$-vertex subtree of the above candidate $T$ has at most one branch vertex, and if it has one, at most two of its arms have length $>1$, because all branching in $T$ occurs at the single high-degree vertex on the main path.

But in $W$, any $8$-vertex subtree with at most one branch vertex must be the subdivided claw with arm lengths $(3,2,2)$: centered at either $c$ or $u$. Thus it has three arms of length $>1$. Any other $8$-vertex subtree of $W$ has at least two branch vertices. Therefore no $8$-vertex subtree of $W$ is isomorphic to an $8$-vertex subtree of any radius-$5$ candidate $T$.

So $\rho(T,W)\ge 6$ for every possible radius-$5$ candidate $T$. Hence no vertex of $\mathscr G_{13}$ has eccentricity $5$, and

Thus Conjecture 1 is disproved.

Citation: Problem source: Bohdan Zelinka, “A distance between isomorphism classes of trees,” Czechoslovak Mathematical Journal 33(108) (1983), 126–130, Conjecture 1. The counterexample above is not cited from the literature.