¿Cuántos vértices de grado 1 hay en un árbol?

Question

¿Cuántos vértices de grado 1 hay en un árbol sin vértices de grado superior a 4? Lo único que tengo por ahora es que el número de aristas de un árbol es n -1 donde n es el número de vértices. Cualquier ayuda se agradecería. Gracias de antemano.

Answer 1

Dejemos que $k$ sea el número de hojas del árbol. Sea $n$ sea el número de vértices.

Se sabe que $k \geq 2$ con igualdad para $T=P_n$ .

En cuanto al límite superior, la suma de grados es como máximo $k+4(n-k)$ . Así,

$$2(n-1)\leq k+4(n-k)=4n-3k \,$$

Resolviendo esta igualdad obtenemos

$$k \leq \frac{2n+2}{3} \,.$$

Desde $k$ es un número entero, debemos tener

$$k \leq \lfloor \frac{2n+2}{3} \rfloor \,.$$

Se puede alcanzar el límite superior. Sea $r$ sea el resto cuando $2n+2$ se divide por $3$ . Entonces (como sugiere la prueba anterior) necesitamos construir un árbol con $\lfloor \frac{2n+2}{3} \rfloor$ hojas, $r$ vértices de grado $2$ y $n-r- \lfloor \frac{2n+2}{3} \rfloor$ vértices de grado $4$ . Se puede demostrar que dicho árbol existe por inducción en $n$ El $P(n) \Rightarrow P(n+3)$ es fácil (sustituir una hoja por un vértice de grado $4$ y conectarlo a 3 nuevas hojas).

Answer 2

Si hay $n_i$ vértices de grado $i$ , $1\le i\le 4$ , entonces debemos tener $$n_1+2n_2+3n_3+4n_4=2(n-1)=2(n_1+n_2+n_3+n_4-1),$$ por lo que $$n_1=n_3+2n_4+2. $$ Especialmente, $$ 2\le n_1\le \frac{2n+2}3.$$ (Este último de $3n_1= 2(n_1+n3+n_4)+2-n_3\le 2n+2$ ).