Let T be a tree with n vertices. Prove that there is a vertex v of T such that each connected component of T −v has at most n/2 vertices. (Remember that T −v is the graph obtained from T by removing v and all edges incident to v
How can I prove this? Please give me some hint to prove this.
Pick an arbitrary vertex $v$ and suppose that $T-v$'s largest component is major, i.e. has more than $n/2$ vertices. There can be at most one major component; because $T$ is a tree, exactly one vertex in this major component (if it exists) – call it $w$ – is adjacent to $v$.
Now move the removed vertex from $v$ to $w$. The size of the largest component in $T-w$ must decrease from that in $T-v$: the major component in $T-v$ has a vertex removed from it and may split into smaller components, whereas the combined vertex count of all other components in $T-v$, possibly reconnected by the no-longer-excluded $v$, remains at most $n/2$.
Since $n$ is finite, we only need a finite number of such vertex shifts to reach the point where the largest component size in $T-v$ is $n/2$ or less, proving the theorem.