Suma del número de vértices de un grafo

Question

Pregunta

Sea $T$ sea un árbol en $100$ vértices. Sea $n_{i}$ el número de vértices de $T$ que tienen exactamente $i$ vecinos. Sea $$s= \sum_{i=1}^{100}\,\, i . n_i$$ ¿Cuál de las siguientes afirmaciones es cierta?

$A)s=99$

$B)s=198$

$C)99 \: < \: s \: < \: 198$

$D)$ Ninguna de las anteriores

Mi enfoque

Simplificando, lo asumí como sesgada Así, cada vértice que no sea hoja tendrá exactamente $1$ vecino y único nodo hoja( $100^{th}$ vértice) tendrá $0$ vértice.

$$s=\sum_{i=1}^{100}\,\, i . n_{i}$$

$$s=1*1+2*1+3*1+....99*1+100*0$$

$$s=4950$$

Así que no debería ser ninguno de estos.

¿Estoy en lo cierto?

Answer 1

No. En un árbol sesgado hay $98$ vértices con dos vecinos, y dos vértices con $1$ vecino. Entonces $n_1=2$ y $n_2=98$ y $n_i=0$ para $i\ge 3$ . $$s=1\cdot 2+2\cdot 98=198$$

De hecho, un árbol con $n$ vértices tiene $n-1$ bordes, y puedes pensar $s$ como el recuento de aristas del árbol, pero cada arista se cuenta tantas veces como vértices tenga la arista, es decir, dos veces.

Answer 2

Pista: Intenta pensar en tu suma en términos de aristas; ¿cuántas veces se cuenta cada arista? Para ver un spoiler, echa un vistazo a este lema .