The most famous question in the history of graph theory. But did someone say Matt Damon?

Certainly not the most important, in fact it’s pretty basic. YOU CAN DO IT YOURSELF!

(the author just thinking - ok actually Matt Damon courtesy of Miramax)

(first published on my substack where you can get #NerdNews, marvellous maths and general geekery)

Good Will Nerding.

The year is 1997. When one of the most famous mathematical problems in pop culture occurs in the movie Good Will Hunting.

In fact the challenge, written up by a lecturer on a chalkboard in the corridor of the maths department, gained such widespread non-maths-world fame through the Academy Award-winning film, it is often called the ‘Good Will Hunting Problem’.

The challenge:

‘Draw all the homeomorphically irreducible trees with n = 10.’

This isn’t the easiest thing to understand off the top of your head, but let’s walk it through.

Let's maths this!

In mathematics, a ‘tree’ is a specific type of graph. A tree is simply a group of points, or ‘nodes’ joined by lines, with only one path between any two nodes. This graph would be a tree with 6 nodes.

This graph would not be a tree, though, because the loop involving nodes 0, 1 and 2 means there are two different ways to get from 0 to 2 — you can go from 0 directly to 2 or from 0 to 1 to 2.

Ok that's a tree, but I want to Damon this!

The ‘with n = 10’ bit is easy — we just need 10 nodes.

But the really tasty bit in the question, to the non-math-

ematical eye, is that the trees have to be ‘homeomorphically irreducible’. This isn’t as bad as it sounds.

It just means that no node has exactly two lines attached to it. That is, every node in a path is a start point, an end point, or a junction of three or more lines.

So while our first tree on the left is, well, a tree, it’s not ‘homeomorphically irreducible’ because we could remove the node labelled 5 and the new tree (like the third graph on the left) would be essentially the same as far as we are concerned.

The tricky thing when you are trying to draw all these trees is that it is sometimes difficult to tell that two trees are actually the same.

For example, these two trees of degree 8 on are actually the same.

You can see that, if you simply spin these branches around this way ...

Got it? Care to have a shot at the ‘Good Will Hunting Problem’?

Turns out Good Will Hunting is a comedy!

And I should note one thing about the movie that every mathematician finds hilarious.

While I admitted the problem is a bit of a mouthful at first, in the film Professor Gerald Lambeau, an absolute gun who is said to have won a Fields Medal (Maths’ Nobel prize!), suggests it took the entire faculty 2 years to work out this problem.

“However, my colleagues and I have conferred, and there is a problem on the board right now that took us more than two years to prove."

With respect Prof, you probably need to get some smarter people in your faculty!

Even by Hollywood standards this is an outrageously inflated claim. Have a crack yourself and see if you can improve on this ‘2 years for a whole faculty’ benchmark.

You’re trying to find 10 different trees.

Maybe you’d like to start by trying to find the ‘4 homeomorphically irreducible trees of order 8’.

Good luck.

Hey, I'm also on Substack.