Generating Homeomorphically Irreducible Trees

Solving the Blackboard Problem in the Movie

“Good Will Hunting”

 

In the movie, Good Will Hunting (1997), a mathematics professor challenges his students to draw all Homeomorphically Irreducible Trees of Order Ten, that is, a collection of trees each having ten dots connected by lines.  The well-known blackboard problem in the movie poses a formidable challenge, especially for larger trees having twenty or thirty nodes.  It would require an extremely large blackboard to draw all the trees, as well as to erase those deemed redundant or incorrect.  This paper explains a SAS® solution for generating Homeomorphically Irreducible Trees of order N.