Show that every finite and undirected tree has either one or two adjacent centres.

52 Views Asked by At

Is this proof vigorous enough? (Feel free to provide any suggestions for improvement as well).

(A centre of a connected graph $G$ is a vertex $v$ with the property that the maximum of the distances between $v$ and all other vertices of $G$ is as small as possible.)

Note: I will not prove the tree properties listed here.

Declarations:

Let $T$ be any tree, $C$ be the set of centres of $T$, and $X$ be the set of end-vertices of $T$.

Let $a(x)$ be the vertex adjacent to $x\in X$.

Let $L(v)$ be the sum of distances between vertex $v\in T$ and all other vertices in $T$ (It is unnecessary to distinguish distance and maximum distance in a tree since there is only one path between any pair of vertices). Note that for all $c\in C$, $L(c)=\text{min}[L(v):v\in T]$.

Let $T'$ be a tree after $X$ is removed from $T$ (since no edges are added to $T$, $T'$ is still a tree) and $C'$ be the set of centres of $T'$.

Let $L'(v')$ be the sum of distances between vertex $v'$ and all other vertices in $T'$. Note that for all $c'\in C'$, $L'(c')=\min[L'(v):v'\in T']$.

Claim 1: $|X|>0$ if $|T|>1$.

Proof 1:

Assume $|X|=0.$ So, $\sum_{v\in T}\deg(v)\ge 2|T|$. By the handshaking lemma, $|E(T)|\ge |T|$. However, one of the tree properties states that $|E(T)| = |T| - 1 \le |T|$. Proven by contradiction.

Claim 2: For all $u,v\in T'$, if $L'(u)<L'(v)$, then $L(u)<L(v)$.

Proof 2:

Let $l'(a,b)$ be the distance between vertex $a$ and vertex $b$ in $T'$. So, for all $u'\in T', L'(u')=\sum_{v'\in T'}l(u',v')$.

Note that for all $u'\in T',L(u')=L'(u')+ \sum_{x\in X} [l'(u',a(x))+1]$. (The distance between $a(x)$ and $x$ is $1$).

Since $L'(u)<L'(v)\implies \sum_{x\in X} [l'(u,a(x))+1] < \sum_{x\in X}[l'(v,a(x))+1]$, $L(u)<L(v)$.

Claim 3: $C=C'$.

Proof 3:

Assume $C\neq C'$. So, for all $c\in C$ and $c'\in C'$, $L(c)<L(c')$ and $L(c)>L(c')$. This is contradictory to Claim 2.

Also, for all $x\in X$, $L(x)=L(a(x))+|T|-1$ ($x$ is always an additional distance away from all other vertices when compared to $a(x)$). $L(c)<L(a(x))<L(x)\implies L(c)<L(x)$ so $x$ cannot be a centre (it is visually obvious as well).

So $C=C'$.

Proof:

Let us keep removing end-vertices from $T$ ($T\to T'\to T'' \to ...$) as long as there are non-end vertices. So, for any tree, it will be until $|T|\le2$ (Claim 1). Hence, there will either be a single vertex or two adjacent vertices left (we cannot remove the remaining vertices, even if they are end-vertices, since it will left us with nothing)

Given that the centres of a tree are preserved after the removal of its end vertices (Claim 3) and all trees are left with one or two adjacent vertices after repeated end-vertices removal, all trees have one or two adjacent centres.