Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The question is :

B-3 Bisecting trees Many divide-and-conquer algorithms that operate on graphs require that the graph be bisected into two nearly equal-sized subgraphs, which are induced by a partition of the vertices. This problem investigates bisections of trees formed by removing a small number of edges. We require that whenever two vertices end up in the same subtree after removing edges, then they must be in the same partition.

a. Show that we can partition the vertices of any n-vertex binary tree into two sets A and B, such that $|A| \leq \frac{3n}{4}$ and $|B| \leq \frac{3n}{4}$, by removing a single edge.

The proof I came up with is using induction on the number of nodes.

Assume that we can partition a tree with (n - 1) nodes in way that fulfills the requirement. To prove we can also do it on a n nodes tree G, first remove a leaf node v from the tree and partition it, which result in 2 binary tree A' and B', which has property

$$ \frac{(n-1)}4 \leq |A'|, |B'| \leq \frac{3(n-1)}4 $$

Without loss generality, we assume that v's parent is in A'. We put v back to A', got 2 tree, A'' and B''. If and A'' still B'' fulfill the requirement for n, then we get the partition we need.

On the other, if adding back v breaks the requirement, it means

$$ \frac{3n}4 \lt |A''| = |A'| + 1 \leq \frac{3n + 1}4 $$

Since A'' is a binary tree with less than n nodes, we can find a partition A''', B''' of A'', which has the property

$$ |A'''| \leq \frac{3}4 |A''| \leq \frac{9n + 3}{16} \leq \frac{3n}4 $$

Without loss generality, we can assume $|A'''| \geq |B'''|$, which means

$$ |A'''| \geq \frac{|A''|}2 \gt \frac{3n}{8} \gt \frac{n}4 $$

Therefore, A''' and G - A''' is a partition for G which fulfills the requirement.


Edit : proof of the base case.

For $ n = 1 $, the proposition doesn't apply as there no way to partition it to 2 nonempty set.

For $ n = 2 $, there's only 1 edge in the tree. By removing this edge, we get 2 sets, A, and B which are

$$ 2 * \frac1{4} = \frac1{2} \lt |A|, |B| \lt 2 * \frac3{4} = \frac3{2} $$

So A and B is a eligible partition. The proposition holds for base case $ n = 2 $.


Is my proof correct? Any simpler proof exist?

(I Google a while but didn't find any solution for the question, so I guess it might be useful to write down my proof as it might be useful for other people.)

share|improve this question
    
+1 for showing some significant thought. You need to show the base case of n=2 (and complain that it is false for n=1). –  Ross Millikan Sep 6 '11 at 3:56
add comment

2 Answers

up vote 3 down vote accepted

The standard proof is algorithmic. Root your tree arbitrarily, and execute the following algorithm. Start with the root $r$. Define a sequence $v_0 = r,v_1,\ldots$ as follows: for each $i$, $v_{i+1}$ is the child of $v_i$ with the larger subtree size (break ties arbitrarily). The sequence ends at some leaf $v_N$.

Denote by $T(v_i)$ the size of the subtree rooted at $v_i$. Since $T(v_0) = n$ and $T(v_N) = 1$, there must be some first $i$ such that $T(v_i) \geq (3/4)n$ and $T(v_{i+1}) < (3/4)n$. If $v_{i+1}$ is the only child of $v_i$ then $T(v_i) = (3/4)n$, and so disconnecting $v_i$ from its ancestor, we're done.

Otherwise, let $w$ be the other child of $v_i$. Since $T(v_i) \geq T(w)$, we have $$(3/4)n \leq T(v_i) = 1 + T(v_{i+1}) + T(w) \leq 1 + 2T(v_{i+1}).$$ Therefore for $n \geq 4$, $$n/4 \leq (3n-4)/8 \leq T(v_{i+1}) < (3/4)n,$$ and so disconnecting $v_{i+1}$ from $v_i$, we're done. If $n < 4$ then a case-analysis suffices.

share|improve this answer
    
Nice proof; I was thinking how to implement the $T(v_i)$. What do you think about this: We do DFS starting from an arbitrary root. and enumerate levels(of vertices; level(root) = 0; ...). Then start from the highest depth( highest level, i.e. leaves) and incrementally assign $T(v_i)$ values(from bottom to top). What to you think? –  Daniel Feb 13 '13 at 1:54
    
And something else: If we were looking for such a "vertex" I guess the same argument works. Right? –  Daniel Feb 13 '13 at 2:31
    
DFS should work. Once you've calculated $T(v_i)$, you can just follow the algorithm. –  Yuval Filmus Feb 13 '13 at 6:38
add comment

How can you proof that the B''' can be connected with B'' after your make G-A''' ? Maybe after you get the A''', the B''' cannot link back to B''.

share|improve this answer
    
This is a tree, and $v_{i+1}$ is not a leaf( $T( {v_{i+1}} )> n/4 $ ). –  Daniel Feb 13 '13 at 1:22
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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