Recursive Property of Trees

42 Views Asked by At

Consider a tree $T$, and consider when we delete a vertex $v$ from $T$ that the remaining connected components are consider branches at vertex $v$. I would like to show that every tree has a vertex such that every branch at this node contains at most half the vertices in a tree.

At first, this felt like a relatively intuitive result, although I have found formally proving it to be somewhat difficult. Assume for the sake of contradiction that for every vertex $v \in T$, there is a branch at $v$ that contains more than half of the vertices in the tree. Let us consider this branch $B$. We realize that for each $v_B \in B$, there is a branch at $v_B$ on $T$ that contains more than half of the vertices. However, I am wondering if this contradicts the relationship that $v$ has to $B$ along with the relationship that $v_B$ has to $B$. Any recommendations on how to move forward with this proof?

1

There are 1 best solutions below

0
On BEST ANSWER

HINT: Start at an arbitrary vertex $v_0$. By assumption there is an adjacent vertex $v_1$ whose branch at $v_0$ contains more than half the vertices of the tree. Continue constructing a walk in the tree: given $v_k$, there is a vertex $v_{k+1}$ whose branch at $v_k$ contains more than half the vertices of the tree. Since the tree is acyclic, there must be some $k$ such that $v_{k+2}=v_k$: at $v_{k+1}$ the walk returns to $v_k$. Get a contradiction at this point.