0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.