1
$\begingroup$

I am looking to prove the following:

Each binary tree with $n \ge 2$ nodes has an edge whose removal results in two trees, each having at most $\lceil (2n-1)/3 \rceil$ nodes.

I am not sure how to approach this, or find some way to detect such an edge. Would appreciate any hints.

$\endgroup$
0
2
$\begingroup$

Root the binary tree at an arbitrary node. Starting at the root, go down the tree, always choosing the node whose subtree is larger, until reaching a node $v$ whose subtree contains at most $\lceil (2n-1)/3 \rceil$ nodes. Remove the edge between the node and its parent.

By construction, the subtree rooted at the parent of $v$ contains $m > \lceil (2n-1)/3 \rceil$ nodes. Since when going down we always choose the node whose subtree is larger, this means that the subtree rooted at $v$ contains at least $(m-1)/2$ nodes, and so the rest of the tree contains at most this many nodes: $$ n - \frac{m-1}{2} \leq n - 1 -\frac{\lceil (2n-1)/3 \rceil}{2}. $$ The right-hand side ought to be bounded by $\lceil (2n-1)/3 \rceil$.

$\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.