Recortes en árboles binarios completos

Question

Reclamo: Supongamos que tenemos un árbol binario completo de altura $h$. Introducimos un corte para dividir este árbol en dos conjuntos de vértices de tamaño $x$ y $2^h - 1 - x$ para algún $x$. Para cualquier $x$, definimos el tamaño óptimo del corte como el número mínimo de aristas que cruzan de un lado del corte al otro lado. Para todos los valores de $x$, vemos cuál es el tamaño óptimo del corte y tomamos el máximo de estos valores. Llamemos a eso $m$. Entonces, no hay un $x$ para ningún $h$ tal que el tamaño óptimo del corte para tanto $x$ como $x+1$ vértices sea $m.

Nota: No sé si este reclamo es cierto.

¿Alguien puede probar esto?

Answer 1

Considera el árbol completo con 3 vértices. Claramente, cuando $x = 1$, el corte óptimo es 1. Sin embargo, cuando $x=2$, el corte óptimo será el mismo, pero con las particiones invertidas, por lo que la afirmación es falsa.