Let $S$ be a finite set whose cardinality is more than 1 and $d: S\times S\rightarrow\mathbb R$ be a positive symmetric function (that is, $d$ is a distance without the axiom of triangle inequality). For a subset $A, B$ of $S$ let $D(A) =\max_{(u,v)\in A^2} d(u,v)$ and $\mu(A,B) := \max\{D(A), D(B)\}$. Consider the problem of minimizing $\mu(A,B)$ subject to the condition that $A\uplus B=S$.
Consider a tree $T$ whose vertex set is $S$. Let $l(T) := \sum_{uv\in E(T)}d(u,v)$, where $E(T)$ is the edge set of $T$. Noting that $T$ is 2-colorable, let $S_T$ be the set of elements of $T$ painted by one color and $S^\prime_T$ be the ones painted by the other.
I would like to show that if $T$ is such that $l(T)$ is maximum, $\mu(S_T,S^\prime_T)$ is minimum.
I would be grateful if you could give a clue as to how to prove the statment (not necessarily a complete proof).
Hint: Let $d^*$ be the value of the optimal solution (that is, the minimum value of $\mu (A,B)$ over all partitions $(A,B)$ of $V$). Consider a maximum-cost spanning tree $T$. Let $\rho$ be the shortest path distance in $T$: $\rho(u,v)$ is the number of edges in the path between $u$ and $v$ in $T$.
We need to show that $d(u,v) \leq d^*$ for every $u$ and $v$ at even distance $\rho(u,v)$. Assume to the contrary that there exist $u$ and $v$ s.t. $d(u,v) > d^*$ and $\rho(u,v)$ is even. Then the path between $u$ and $v$ in $T$ and edge $(u,v)$ form a cycle $C$.
Show that