Bona "A Walk Through Combinatorics" Problem 10.29

176 Views Asked by At

Given a tree $T$, define the "total distance" of a vertex $v$ by $$ td(v) = \sum_{w \in V(T)} d(v,w), $$ where $d(v,w)$ is the number of edges in the unique $vw$-path in $T$. In any tree, the value of $td$ is minimized by at most two vertices (these vertices coincide with the more standard definition of "center").

Bona provides a terse solution: If there were three such vertices, some two of them (say $u$ and $w$) would not be connected by an edge. Let $v$ be any vertex lying strictly between $u$ and $w$ on the unique $uw$-path. It follows that $td(v)$ is smaller than one of $td(u)$ or $td(w)$, which is a contradiction.

I'm having a difficult time giving a convincing argument for the bolded assertion. I keep finding myself trying to use the fact that there are "plenty" of vertices $x$ such that $d(a,x) = d(a,z) + d(z,x)$, but there are also vertices for which the reverse is true ($a$ is closer to the vertex than $z$). What can be said to bring this contradiction out more explicitly?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $U$ be the set of vertices in the component of $T-v$ containing $u.$

Let $W$ be the set of vertices in the component of $T-v$ containing $w.$

Let $S=V(T)\setminus(U\cup W).$

Then $V(T)$ is partitioned into disjoint nonempty sets $U,W,S.$ Without loss of generality, assume that $|U|\le|W|\lt|S\cup W|.$

For any vertex $x\in V(T)$ we have $d(u,x)\ge d(v,x)-d(u,v).$

For any vertex $x\in S\cup W$ we have $d(u,x)=d(v,x)+d(u,v).$

Hence $$td(u)=\sum_{x\in V}d(u,x)=\sum_{x\in U}d(u,x)+\sum_{x\in S\cup W}d(u,x)$$ $$\ge\sum_{x\in U}[d(v,x)-d(u,v)]+\sum_{x\in S\cup W}[d(v,x)+d(u,v)]$$ $$=td(v)+(|S\cup W|-|U|)d(u,v)\ge td(v)+d(u,v)\gt td(v),$$ contradicting the assumed minimality of $td(u).$