He interpretado mal la pregunta para decir que los vértices son también de color, por lo que un vértice no se puede incidente para conectar dos bordes rojos, mientras que también siendo incidente para conectar dos bordes de color negro. La interpretación correcta es que sólo el interior de los bordes es de color - los vértices están sin colorear (o tal vez multicolor es una buena manera de pensar en ella). Así, un conjunto de $S$ de puntos rojos está conectado si $S$ está en el mismo componente conectado del árbol cuando se elimina la parte de color negro.
Afortunadamente, podemos reducir el problema original para el problema que yo estaba pensando. El Color de cada vértice de la raíz, de acuerdo a la más cercana de color utilizado en la arista que conduce a la raíz de vértice, y el color de la raíz de forma arbitraria. Cada componente se divide en en la mayoría de los tres componentes de este proceso. Así que si el árbol original tenía $n'$ de los componentes conectados, el nuevo árbol tiene en la mayoría de las $n=3n'$ de los componentes conectados. El uso de esta $n$ en el siguiente argumento.
Sí, podemos usar cualquier $h$ con $3^h>2(n+1)3^n.$
Deje $R_1,\dots,R_r$ ser los componentes conectados de la parte roja, y $B_1,\dots,B_b$ los componentes conectados de la parte azul.
Para cualquier conjunto a$S$ deje $S^*$ denota el conjunto de todos los puntos de $p$ tal que el camino más corto de $p$ a la raíz del árbol pasa a través de $S.$ (algo así como tomar todos los descendientes, pero con inclusión de los puntos en los bordes).
Si la raíz del árbol es de color rojo, entonces la longitud total de la parte roja es
$$L(R_1\cup\dots\cup R_r)=L(R^*_1)+\dots+L(R^*_r)-L(B^*_1)-\dots-L(B^*_b)$$
donde $L$ significa que la longitud total. Esta es una forma de exclusión-inclusión de la fórmula.
Para cualquier conjunto conectado a$S$ hay un único punto de $p$ en el cierre de $S$ más cercano a la raíz. La distancia de $p$ a una hoja puede ser escrito como $d_0+D$ donde $D$ es un número entero y $d_0\in[0,1)$ si $p\in S,$ e $d_0\in(0,1]$ si $p\not\in S.$ Luego
$$L(S^*)=d_0+3+3^2+\dots+3^D=d_0+\tfrac32(3^D-1).$$
Por ejemplo, si $S^*$ consiste en un vértice, el niño de tres hojas y los bordes en el medio, entonces $D=1$ e $L(S^*)=3.$
La longitud total del árbol es $\tfrac32(3^h-1).$ por Lo que es suficiente para mostrar que una suma de $n$ números de la forma $\pm (d_0+\tfrac 32(3^D-1))$ no puede igualar $\tfrac34(3^h-1).$
Dividiendo por $\tfrac32 3^h,$ queremos mostrar que una suma de $n$ números de la forma $\pm 3^{D-h}$ no puede igualar $\tfrac 12$ a dentro de aditivo de error $3^{-h}(n+1).$
El uso de $3^h>2(n+1)3^n$ esta de la siguiente manera:
Para un entero $n\geq 1$ y enteros $x_1,\dots,x_n,$ tenemos $$|\pm 3^{x_1}\pm\dots\pm 3^{x_n}-\tfrac12|\geq \tfrac12 3^{-n}.$$
El uso de las reglas de $3^x+3^x=3^{x+1}-3^x$ , se puede reducir al caso en que el $x_i$ son distintos - un equilibrio ternario de la representación. Wlog $x_1$ es el más grande. La suma de $3^{x_1}\pm\dots\pm 3^{x_n}$ se encuentra en el rango $(\tfrac12 3^{x_1},\tfrac 32 3^{x_1}),$ lo que significa que hemos terminado, a menos que $x_1\in\{0,-1\}$ - no necesitamos considerar los casos donde $3^{x_1}\pm\dots\pm 3^{x_n}$ es de menos de $\tfrac16$ o mayor que $\tfrac32.$
El caso de $n=1$ es sólo la aritmética: $|1-\tfrac12|,|\tfrac13-\tfrac12|\geq \tfrac16.$
Para $n>1$ podemos utilizar la inducción; la cantidad de $t=\pm 3^{x_2}\dots\pm 3^{x_n}$ satisface $|-t-\tfrac 12|,|t-\tfrac 12|\geq \tfrac12 3^{-(n-1)}.$ Para $x_1=0$ uso de $$|1+t-\tfrac12|=|t+\tfrac12|=|-t-\tfrac12|\geq\tfrac12 3^{-(n-1)}\geq\tfrac12 3^{-n}.$$
Para $x_1=-1$uso
$$|\tfrac13+t-\tfrac12|=\tfrac13|3t-\tfrac12|\geq \tfrac12 3^{-n}.$$
