15
$\begingroup$

I don't know if any of you have seen the movie "Good Will Hunting" but there is a particular mathematics problem in the movie that is of interest to be. One of the problems used in the movie is

"Draw all homeomorphically irreducible trees of size $n = 10$."

I've been able to draw all ten valid trees and have confirmed that these are correct and are the only solutions. However, does anyone know how you would go about proving that there are only ten valid trees? I've thought of approaching the problem inductively but it quickly becomes very complicated. Any advice?

For reference, here is an image of the ten valid trees: http://25.media.tumblr.com/tumblr_lm8kawOpTO1qcj2hco1_400.png.

enter image description here

$\endgroup$
14
$\begingroup$

Denote the number of vertices with degree $k$ by $n_k\geq0$. Then $n_2=0$ and $n_k=0$ for $k>9$. Therefore we have $$n_1+n_3+n_4+n_5+n_6+n_7+n_8+n_9=10\ .$$ Since a tree with $10$ vertices necessarily has $9$ edges we also have $$n_1+3n_3+4n_4+5n_5+6n_6+7n_7+8n_8+9n_9=18\ .$$ Subtracting these two equations we obtain the necessary condition $$2n_3+3n_4+4n_5+5n_6+6n_7+7n_8+8n_9=8\ .\tag{1}$$ Let $r=\max\{k\>|\>n_k\ne0\}$. We now list the possible solutions of $(1)$ according to descending $r$, beginning with $r=9$. Not mentioned $n_k$'s with $k>1$ are tacitly $=0$.

$r=9$: $\quad n_9=1$ enforces $n_1=9$, which is Nr. 8 in the picture.

$r=8$ is impossible.

$r=7$: $\quad n_7=1$ enforces $n_3=1$, whereby the $7$-vertex and the $3$-vertex have to be adjacent. This is Nr. 1 in the picture.

$r=6$: $\quad n_6=1$ enforces $n_4=1$, whereby the $6$-vertex and the $4$-vertex have to be adjacent. This is Nr. 2 in the picture.

$r=5$: $\quad n_5=2$ enforces $n_1=8$, which is Nr. 6 in the picture. – $\quad n_5=1$ enforces $n_3=2$. The two $3$-vertices and the $5$-vertex can be arranged as $353$ or as $335$. These are Nr. 4 and Nr. 9 in the picture.

$r=4$: $\quad n_4=2$ enforces $n_3=1$. The two $4$-vertices and the $3$-vertex can be arranged as $434$ or as $443$. These are Nr. 10 and Nr. 3 in the picture. – $\quad n_4=1$ is impossible.

$r=3$ enforces $n_3=4$. The four $3$-vertices can be in line or in the form of a propeller. These are Nr. 7 and Nr. 5 of the picture.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.