Lagmental Vicfred

Tree Metrics Satisfy the Four-Point Condition by Vicfred

tags: mathematics, trees, graph distance, structural graph theory

Among three pairwise distance sums for four vertices in a weighted tree, the two largest are equal. I want the notation, the mechanism, and the failure mode visible at the same time.

Notation

A finite graph \(T=(V,E)\) is a tree when it is connected and acyclic. The unique simple path \(P_{uv}\) between two vertices makes distance and recursive decomposition especially rigid.

$$ S_1=d(a,b)+d(c,d),\quad S_2=d(a,c)+d(b,d),\quad S_3=d(a,d)+d(b,c) $$

A reliable calculation names domain and codomain. The notation \(\mathsf{data}\mapsto\mathsf{claim}\) is harmless only after both \(\operatorname{dom}\) and \(\operatorname{cod}\) have been fixed.

$$ \max\{S_1,S_2,S_3\}\ \text{is attained at least twice} $$

Stress the formula

A worked instance is useful here because it exposes every index that the compressed statement hides.

$$ \operatorname{sort}(S_1,S_2,S_3)=(s,\ s+2\ell,\ s+2\ell)\qquad(\ell\ge0\text{ is the central path length}) $$

Interpretation

What survives the example is not its particular numbers but the relation encoded by the two rows below. That relation is the part worth transporting to a new setting.

$$ \begin{aligned} \mathsf{D}\;&:\quad S_1=d(a,b)+d(c,d),\quad S_2=d(a,c)+d(b,d),\quad S_3=d(a,d)+d(b,c),\\[5pt] \mathsf{C}\;&:\quad \max\{S_1,S_2,S_3\}\ \text{is attained at least twice}. \end{aligned} $$

Limit of the argument

A rooted tree adds a parent relation that an unrooted tree does not possess. Statements about ancestors depend on the chosen root.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \max\{S_1,S_2,S_3\}\ \text{is attained at least twice} \end{gathered}} $$

The result is compact enough to reuse without pretending that the caveat has disappeared. The worked line remains the quickest consistency check.

This article was posted on Thu 21 May 2009. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.