Prove that the centroid of any tree, $T$, is either a single vertex or 2 vertices which are connected by an edge in $T$.

3k Views Asked by At

I am quite new to mathematics and, especially, how to write proofs. So, I usually try to find "solutions" to verify with the "proof"s I come up on my own. Unfortunately, for the proposition stated in the title, I could not find any source to verify it. Any input, substantive or regarding style, would be very helpful for me.

The definition of the centroid of a tree graph is given as follows:


Let $T=(V,E)$ be a tree and $v$ some vertex of $T$. Put $$\tau(v) = \max\{|V(T_1)|,|V(T_2)|,...,|V(T_k)|\},$$ where $T_1,T_2,...,T_k$ are all the components of the graph $T-v$, i.e., the graph $T$ with the vertex $v$ and all edges involving $v$ removed from it. The centroid of the tree $T$ is the set of all vertices $v\in V$ with the minimum value of $\tau(v)$.


This is how far I came with my "proof":

For a tree of two vertices, the centroid coincides with the graph and, thus, the statement holds. Suppose, therefore, that $n\ge 3$. If there exists a unique $v^* \in V$ such that $v^* = \text{argmin}_{v\in V} \tau(v)$, then we are done. If not, suppose that there exists a set $C(T)$ consisting of at least two distinct vertices, $x$ and $y$. We first show that if $x,y\in C(T)$, then $\{x,y\} \in E(T)$.

Let $\mathcal A(v)$ be collection of components that are created by deleting $v$ from $T$ and, further, let $A(v)$ be the largest of these components. As both of $x,y$ are elements of $C(T)$, it must be the case that $|A(x)|=|A(y)|$.

As $T$ is a tree, there exists a unique path $P(x,y)=\{x,...,y\}$ connecting $x$ and $y$. If $x\notin A(y)$, then it must be the case that $|A(x)|>|A(y)|$, since $A(y)\subset \Big(P(x,y)\setminus\{x\}\Big)\cup A(y) \in \mathcal A(x)$. Therefore, $x\in A(y)$ and, by symmetry, $y\in A(x)$.

Now, suppose that there exists a nonempty set of vertices $W \subset P(x,y)$, which are distinct from $x$ and $y$. Clearly, as $x\in A(y)$ and $y\in A(x)$, $w \in A(x)\cap A(y)$ for all $w\in W$. But then, for all $w\in W$, $\mathcal A(w)$ will consists of components which are strict subsets of either $A(x)$ or $A(y)$. Hence, we have $\tau(w)<\tau(x)$, for all $w\in W$, which contradicts the assumption that $x \in C(T)$. Therefore, if both $x$ and $y$ are elements of $C(T)$, then $W=\varnothing$ and $P(x,y)=\{x,y\}\in E(T)$.

Lastly, if there are three distinct vertices $x,y,z\in C(T)$, it follows from the result above that $\{x,y\},\{y,z\},\{x,z\}\in E(T)$. Thus, $T$ must contain a cycle $\{x,y,z,x\}$, which contradicts the assumption that $T$ is a tree. Therefore, $|C(T)|\le 2$.