Draw All Homeomorphically Irreducible Trees of Size

I put an edit in italics to show you where I messed up: maybe you'll see the mistake too before reading the italics!

Fun little post!  I say "open" problem because that's what they call it in your favorite Ben Affleck-Matt Damon movie*, but the problem they pose is actually super easy and by the end of this post, you'll be as good at it as Matt Damon!

Here's the clip from Good Will Hunting:

If you pause the clip at 2:22, you'll see what the "open problem" is:

Draw all the homeomorphically irreducible trees with n=10.

And that's the problem we'll be dealing with today!

So let's review/learn what all these words mean.  Remember, agraphis a drawing of dots connected by lines (see these two posts for examples).  A graph is connectedif you can follow a path from any dot to any other dot.

Left is connected, using the light colored lines (ignoring the three isolated points). The graph on the right is not, since there's no path from the eye to the mouth.

Now a tree is a connected graph without any loops in it: that is, there's no way to start heading out from one dot and get back to that same dot without backtracking down the way you came.

" data-medium-file="https://bakingandmath.files.wordpress.com/2014/05/treesnottress.jpg?w=300" data-large-file="https://bakingandmath.files.wordpress.com/2014/05/treesnottress.jpg?w=490" class="size-large wp-image-1868" src="https://bakingandmath.files.wordpress.com/2014/05/treesnottress.jpg?w=490&h=239" alt="Everything but the "NO" is a tree- there are no loops in the graphs." width="490" height="239" srcset="https://bakingandmath.files.wordpress.com/2014/05/treesnottress.jpg?w=490&h=239 490w, https://bakingandmath.files.wordpress.com/2014/05/treesnottress.jpg?w=150&h=73 150w, https://bakingandmath.files.wordpress.com/2014/05/treesnottress.jpg?w=300&h=146 300w, https://bakingandmath.files.wordpress.com/2014/05/treesnottress.jpg 621w" sizes="(max-width: 490px) 100vw, 490px">

Everything but the "NO" is a tree- there are no loops in the graphs.

One funny thing about graphs: it doesn't matter which way you draw the graph: all that matters is the way the vertices connect with each other.  So for instance, all of the following are the same graph.

No matter how you slice it, it's still a chain of 9 green dots.

So our GWH problem has to do with drawing a bunch of loop-less graphs, with n=10 dots.  There's just one last bit of the problem to learn: just like in the topological setting where we learned about it before, a homeomorphism is a function that sends one picture to another picture by wriggling it around continuously.  This is basically what we did in the picture above.

So when I say give me a list of homeomorphically irreducible trees, I want none of the trees you give me to be "reducible" via a homeomorphism.  Rather than a strict definition, I'll just say that here, homeomorphically irreducible means that none of the dots have exactly two neighbors- if you had such a picture, you could just "erase" that dot and have a picture with about the same amount of information.

The left two graphs are homeomorphically reducible. The rightmost one is irreducible, though that doesn't seem to make it happy.

Instead of diving in to n=10, let's try something a little smaller, like n=3.  Here are all the homeomorphically irreducible trees with n=3:

Ha ha it's a joke!  There aren't any!  If we want to be connected with three dots, there are actually only two possible configurations: a line (maybe kink it around a bit, but it's homotopic to a straight one), and a triangle.  The triangle is a loop, so we can't have that on our list.  The line segment automatically has a vertex in the middle with two neighbors, so it's not homeomorphically irreducible.  So to answer our question,there are no homeomorphically irreducible trees of degree 3.

Okay let's try something more interesting.  Here are all four trees for n=5:

You can tell by the way I track that I'm a tree graph, no time to loop back. Ah, ah ah ah, staying with five, staying with five. Ah ah ah ah, staying with fiiiiiiive.

NOTE!  The blue "F" is homotopic to the blue "4": try to see how you can swing a leg down and reflect for the homotopy.

Here's the mistake!  There are only three trees for n=5.  The bottom left one is the same as the blue F and blue 4 by straightening out the kink.  Thanks to Dan in the comments for pointing this out.

Which of these is homeomorphically irreducible?  Just the last one: all the others have a vertex with only two neighbors.

If you want, you can draw all the homotopically distinct trees for n=6, 7, 8, 9 in this way and get to n=10, but let's try to find a shortcut, shall we?

For this next part, we'll be talking about the degree of a vertex: the number of other vertices attached to it.  For instance, in our bottom right blue "X" graph, we have four dudes with degree 1, and one vertex with degree 4, since the middle one is connected to all four of the outside guys, but each of them only sees her in the center.

So if I go through all the trees with n=5, I have:

1 graph with 2 of degree 1 and 3 of degree 2 (no good)

2 graphs with 3 of degree 1, 1 of degree 2, and 1 of degree 3 (no good)

1 graph with 4 of degree 1 and 1 of degree 4. (ding ding ding!)

What if I go through all the trees with n=4?

1 graph with 2 of degree 1 and 2 of degree 2 (no good)

1 graph with 3 of degree 1 and 1 of degree 3 (ding ding ding!)

This is just a bunch of data as it is, but maybe if I stare at it long enough I'll be able to find a pattern that will help me with the problem.  I'll tell you how I did this problem (literally on the back of a piece of paper right now), and send you to a link as to how to do it using equations.

Looking at the data, I notice that it's a lot easier to start with the highest degree I allow, and build all the graphs from there.  So for instance, with n=5, I can allow highest degrees of 4, 3, and 2 (and allowing 2 is silly because I don't want vertices of degree 2).  So I only need to look at graphs with degrees 4 (there's just the star) and 3 (the upper right and bottom left, which both necessarily include vertices of degree 2).

So for our problem, let's look at the highest degree possible for a graph, and see how many homeomorphically irreducible trees there are with that degree.

Highest degree 10 is impossible, because you need at least 11 vertices for someone to have 10 neighbors.  So we start with 9, which is just a star.  Add it to our list.

How about 8?  Well, if I start with a vertex and give it 8 neighbors, I've got one more vertex to add somewhere.  I can't add it to the central one because it's all neighbor'd out.  If I add it to one of the 8 neighbors, I get a vertex of degree 2.  So there are no homeomorphically irreducible trees of size n=10 with highest degree = 8.

However, I can make one with 7.  Use the reasoning above, but since we're trying to avoid vertices of degree 2, I need to add both of my new vertices to one of the 7 neighbors.  Then do the same with 6- I can't split the three new vertices up between different neighbors, since that'll also result in a vertex of degree 2.

Here's a picture of the cases so far.

I bet Kelly Clarkson would be into these graphs: they're spreading their wings and learning to fly

Not gonna lie, I am getting mighty tired of MS Paint around now.  Phew!  I'll just tell you the degree sequences for the rest of the graphs, and you draw them, how about that?  That way you're more like Matt Damon anyway.

For highest degree 5: 5, 3, 3, and seven vertices of degree 1.  5, 5, and eight vertices of degree 1.  5, 3, 3, and seven vertices of degree 1 (there are two graphs with this degree sequence, but they're different from each other).

There are two graphs with highest degree 4, and two graphs with highest degree 3.

So in total, we have the three trees I drew, and the 3+2+2=7 trees you drew.  That means that we end up with 10 trees, which is exactly what GWH has.  And since we went through all possible combinations of highest degrees and used lots of combinatorial thinking, we've proven to ourselves that this is a complete list.

For an answer without proof, see this video from last year (I didn't know about it when I started this post).

For a more mathy proof, see this link, apparently this answer is due to this Swiss mathematician.

*From googling for the above two links, I realize that in the movie they don't say this is open, but that it took the MIT math professors two years to solve.  I love it!  Also, hello from Ann Arbor, Michigan!  This is just an explanation for the delay- still traveling, just at a fantastic math conference.

Tags: homeomorphism

mckinnonmices1984.blogspot.com

Source: https://bakingandmath.com/2014/05/30/good-will-hunting-open-math-problem-ha/

Share this post