Supongamos que T es un árbol con secuencia de grados 5, 5, 5, 4, 4, 3, 3 más varios 2 y 1. Encuentra el número de hojas de T.

Question

Supongamos que T es un árbol con secuencia de grados 5, 5, 5, 4, 4, 3, 3 más varios 2 y 1. Encuentra el número de hojas de T.

Hasta ahora he progresado hasta esto. Deja que $x$ sea el número de vértices de grado $2$ y $y$ sea el número de vértices de grado $1$ (hojas). Entonces $$|V| = 7 + x + y \implies |E| = 7 + x + y - 1 = 6 + x + y$$ y $$2|E| = 5(3)+4(2)+3(2)+2(x)+1(y) \implies |E| = 29/2 + x + y/2$$ así que $6 + x + y = 29/2 + x + y/2$, eventualmente obtienes $y = 17$.

Pero a partir de aquí, no sé cómo obtener $x$. ¿Tengo el enfoque correcto o me falta algo más?

¡Gracias de antemano!

Answer 1

No te estás perdiendo de nada.

Todo lo que necesitabas hacer es resolver para el número de hojas, que es $y$ en tu notación. El número de vértices de grado $2$, que es $x$, no puede ser determinado solo con esta información, pero tampoco necesitas saberlo para resolver el número de hojas.

De hecho, puedes construir un árbol con secuencia de grados $5,5,5,4,4,3,3$ seguido por $y=17$ unos, donde no hay vértices de grado $2$. A partir de ahí, puedes tomar cualquier arista y subdividirla en un camino de longitud arbitraria, lo que te dará un árbol con secuencia de grados $5,5,5,4,4,3,3$, seguido por cualquier cantidad de doses que desees, seguido por $17$ unos. Por lo tanto, existen árboles en los que $x$ puede ser cualquier número entero no negativo que desees.