Demostrar que cualquier árbol con $n$ nodos tiene al menos $\frac {n}{2}$ nodos con grado $1$ o $2$ . $n \ge 2$

Question

He aquí la cuestión:

Un árbol es un grafo simple conexo sin ciclos.
Demostrar que cualquier árbol con $n$ nodos tiene al menos $\frac {n}{2}$ nodos con grado $1$ o $2$ . $n \ge 2$

---

Intento utilizar la inducción matemática para demostrar esto con el caso base de $2$ . Cada árbol tendrá $n-1$ bordes si hay $n$ vértices. Así que el Caso Base tendrá al menos un nodo con grado de $1$ . Sin embargo, parece que es muy difícil demostrar la $k+1th$ caso. ¿Algún método para abordar esta cuestión? Gracias

Answer 1

Supongamos que hubiera menos de $n/2$ nodos con grado $1$ o $2$ . Si $n$ es par entonces esto significa que hay al menos $n/2+1$ nodos con grado $3$ o más, y si $n$ es impar entonces hay al menos $(n+1)/2$ nodos con grado $3$ o más. Por supuesto, dado que los árboles están conectados, el resto de los nodos tienen grado al menos $1$ .

Ahora toma la suma total de los grados. En el caso par es al menos $3n/2+3 + n/2-1 = 2n + 2$ por lo que, según el lema del apretón de manos, hay al menos $n+1$ bordes. En el caso impar la suma es como mínimo $3(n+1)/2 + (n+1)/2 = 2(n+1) = 2n+2$ también, así que de nuevo hay al menos $n+1$ bordes.

Pero esto es absurdo, ya que sabemos que sólo hay $n-1$ aristas de un árbol en $n$ nodos.