Good Will Hunting Problem

This problem is popularized by the movie "Good Will Hunting"

Courtesy of singingbanana/numberphile for the problem.


Problem:


Draw all homeomorphically irreducible trees of size n = 10.

If you don't know what a mathematical tree is then i'd recommend a quick look at the following two links.

http://en.wikipedia.org/wiki/Tree_(graph_theory)

http://en.wikipedia.org/wiki/Graph_(mathematics)

So below are some trees

Basically a tree is a graph without any cycle. You can consider a tree being a series of dots connected together like a network but with one constraint. It shouldn't have any cycle. Following is a graph with a cycle. Since, it has a cycle it is a graph not a tree.

So, the question asks to draw all  homeomorphically irreducible trees of size 10. 

Mind you that the question isn't just asking to draw all trees of size 10 (size = number of nodes or vertices). It has two phrases "homemorphically and irreducible". That means

Structures like above should be counted as one. They aren't different. If you spread the edges of the second tree you can easily form the first tree. So, if one tree can be shown to be like another tree by stretching the edges then we should consider those trees as being the same tree.

Also, The following trees aren't allowed. As you can see, each has at least one vertex with two edges connected to it. If that was allowed then you could put arbitrary many points between two vertices to make infinitely many different kinds of trees. Those don't make interesting trees. 

So, the problem is to draw all homeomorphically irreducible trees of size n = 10 or 10 vertices.

Give it a try!! 

SPOILER!!!!!!

Below is my approach to solve this problem.

The general strategy that i have used to solve this problem is to start with the principle branch which i define as a node or a collection of nodes connected by a straight line from which edges branch out to form trees. Just like in a tree we have a stem from which branches branch out. You can consider principle branch to be the stem from which edges branch out.

Lets start with one vertex in the principle branch and generate all the possible trees from there.

 The following is obvious.

This one below wasn't so obvious.

Then lets move on to two vertices in principle branch. So, first i start with the principle branch with two vertices and then enumerate all possible trees from there.

Following are all trees with two vertices principle branch.

As you can see, with the principle branch set the problem of generating the different trees is just moving edges from one vertex to another.

Lets move on to three vertices principle branch.  

With this approach, you can easily see when you have exhausted the number of possible trees with that many vertices in the principle branch.

Finally, the only tree possible with 4 vertices principle branch.

This is because if we move any edge from any vertex then that vertex will have one edge less than three which will break our definition of being homeomorphically irreducible tree. We want each vertex of the tree to have at least three edges connected to it.

This concludes the solution to the problem of finding all homeomorphically irreducible trees of size 10 with cap reached at four vertices principle branch.