The Problem from Good Will Hunting

In the film Good Will Hunting the MIT mathematics professors set a challenge to their freshman intake which they say took them two years, but they write it up on a blackboard in the corridor so that any of the ambitious upstarts can prove themselves. The protagonist is working as a janitor at the time and tries to write up his solution covertly, but is noticed by the mathematical powers that be.

Let's have a look at the problem itself. Stated semi formally, you have to draw all homeomorphically distinct, irreducible, trees of order 10.

There's quite a lot of vocab there, so let's break it down. Here is a picture below to help:

We want to draw a graph with 10 nodes which has no cycles within it, which makes it a tree. Homeomorphic graphs are those that you can move the nodes and lines without cutting anything. Rotating it round or picking it up and flipping it over is fine too. We want all of our graphs to be actually distinct.

Finally we want our graphs to be irreducible. If you look at the picture above, that node in the middle isn't really doing anything. You could add as many nodes as you liked along a straight line and name it distinct, which we want to rule out.

It turns out that there are only ten distinct solutions and to get you started here’s one to get you started:

It's a therapeutic process to work them all out, so I've put the full list of solutions slightly down the page in case you want to derive them:

...

They remind me of organic chemistry.

If you are feeling brave and want to experience some university level maths here is a wonderful paper discussing this problem along with all of the other problems seen on screen in Good Will Hunting. They do their best to explain to an undergrad level, but there will be a bit of notation that you are unfamiliar with along the way.