Prueba que implica un problema de "Good Will Hunting"

Question

No sé si alguno de ustedes ha visto la película "Good Will Hunting" pero hay un problema matemático particular en la película que es de interés. Uno de los problemas utilizados en la película es

"Dibuja todos los árboles homeomórficamente irreducibles de tamaño $n = 10$ ."

He podido dibujar los diez árboles válidos y he confirmado que son correctos y que son las únicas soluciones. Sin embargo, ¿alguien sabe cómo se puede demostrar que sólo hay diez árboles válidos? He pensado en plantear el problema de forma inductiva pero rápidamente se complica mucho. ¿Algún consejo?

A modo de referencia, aquí hay una imagen de los diez árboles válidos: http://25.media.tumblr.com/tumblr_lm8kawOpTO1qcj2hco1_400.png .

Answer 1

Denota el número de vértices con grado $k$ por $n_k\geq0$ . Entonces $n_2=0$ y $n_k=0$ para $k>9$ . Por lo tanto, tenemos $$n_1+n_3+n_4+n_5+n_6+n_7+n_8+n_9=10\ .$$ Dado que un árbol con $10$ vértices tiene necesariamente $9$ bordes también tenemos $$n_1+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9=18\ .$$ Restando estas dos ecuaciones obtenemos la condición necesaria $$2n_3+3n_4+4n_5+5n_6+6n_7+7n_8+8n_9=8\ .\tag{1}$$ Dejemos que $r=\max\{k\>|\>n_k\ne0\}$ . Ahora enumeramos las posibles soluciones de $(1)$ de acuerdo con la descendente $r$ , comenzando por $r=9$ . No se menciona $n_k$ 's con $k>1$ son tácitamente $=0$ .

$r=9$ : $\quad n_9=1$ refuerza $n_1=9$ que es el número 8 en la imagen.

$r=8$ es imposible.

$r=7$ : $\quad n_7=1$ refuerza $n_3=1$ por lo que el $7$ -vertex y el $3$ -vértice tienen que ser adyacentes. Este es el número 1 de la imagen.

$r=6$ : $\quad n_6=1$ refuerza $n_4=1$ por lo que el $6$ -vertex y el $4$ -vértice tienen que ser adyacentes. Este es el número 2 de la imagen.

$r=5$ : $\quad n_5=2$ refuerza $n_1=8$ que es el número 6 en la imagen. - $\quad n_5=1$ refuerza $n_3=2$ . Los dos $3$ -verticales y el $5$ -vertex puede disponerse como $353$ o como $335$ . Se trata de los números 4 y 9 de la imagen.

$r=4$ : $\quad n_4=2$ refuerza $n_3=1$ . Los dos $4$ -verticales y el $3$ -vertex puede disponerse como $434$ o como $443$ . Estos son los números 10 y 3 de la imagen. - $\quad n_4=1$ es imposible.

$r=3$ refuerza $n_3=4$ . Los cuatro $3$ -Los vértices pueden estar en línea o en forma de hélice. Se trata de los números 7 y 5 de la imagen.