La pregunta es :
B-3 Árboles bisectores Muchos algoritmos de divide y vencerás que operan en grafos requieren que el grafo sea bisecado en dos subgrafos de tamaño casi igual, que son inducidos por una partición de los vértices. Este problema investiga las bisecciones de árboles formados por la eliminación de un pequeño número de aristas. Exigimos que siempre que dos vértices acaben en el mismo subárbol después de eliminar aristas, entonces deben estar en la misma partición.
a. Demuestre que podemos dividir los vértices de cualquier árbol binario de n vértices en dos conjuntos A y B, tales que $|A| \leq \frac{3n}{4}$ y $|B| \leq \frac{3n}{4}$ eliminando una sola arista.
La prueba que se me ocurrió es utilizando la inducción en el número de nodos.
Supongamos que podemos particionar un árbol con (n - 1) nodos de manera que se cumpla el requisito. Para demostrar que también podemos hacerlo en un árbol de n nodos G, primero eliminamos un nodo hoja v del árbol y lo particionamos, lo que da como resultado 2 árboles binarios A' y B', que tienen la propiedad
$$ \frac{(n-1)}4 \leq |A'|, |B'| \leq \frac{3(n-1)}4 $$
Sin pérdida de generalidad, suponemos que el padre de v está en A'. Volvemos a poner v en A', obtenemos 2 árboles, A'' y B''. Si y A'' aún B'' cumplen el requisito de n, entonces obtenemos la partición que necesitamos.
Por otro lado, si la adición de v rompe el requisito, significa que
$$ \frac{3n}4 \lt |A''| = |A'| + 1 \leq \frac{3n + 1}4 $$
Como A'' es un árbol binario con menos de n n nodos, podemos encontrar una partición A''', B''' de A'', que tiene la propiedad
$$ |A'''| \leq \frac{3}4 |A''| \leq \frac{9n + 3}{16} \leq \frac{3n}4 $$
Sin pérdida de generalidad, podemos suponer $|A'''| \geq |B'''|$ , lo que significa que
$$ |A'''| \geq \frac{|A''|}2 \gt \frac{3n}{8} \gt \frac{n}4 $$
Por lo tanto, A''' y G - A''' es una partición para G que cumple el requisito.
Editar : prueba del caso base.
Para $ n = 1 $ la proposición no se aplica ya que no hay manera de dividirlo en 2 conjuntos no vacíos.
Para $ n = 2 $ , sólo hay una arista en el árbol. Al eliminar esta arista, obtenemos 2 conjuntos, A, y B que son
$$ 2 * \frac1{4} = \frac1{2} \lt |A|, |B| \lt 2 * \frac3{4} = \frac3{2} $$
Así que A y B es una partición elegible. La proposición es válida para el caso base $ n = 2 $ .
¿Es correcta mi prueba? ¿Existe alguna prueba más sencilla?
(He buscado en Google un rato pero no he encontrado ninguna solución para la pregunta, así que supongo que puede ser útil escribir mi prueba ya que puede ser útil para otras personas).
