# The Graceful Tree Problem – Numberphile

What’s this, Brady? It’s like a graph, or joined up circles? No, this is an ant. You can see the antenna up there, and then this is the body of the ant. Oh yeah, OK. We’re going to place odd consecutive integers starting with one into this ant. So, what are those odd consecutive integers starting with one? Well, we need one, three, five, seven, and nine. We’re going to be placing them in here. So, what number do you want here? Seven. Seven, and here? Three. And here? One. Let’s put nine. And? Five. OK, so this is an example of a failure. We’re going to look at five minus one; that is four. 4 9 minus 1 that’s 8 3 minus 1 that’s 2 everything looks different so far looking good Sadly 7 minus 3 is also 4 so we failed this is an example of a failure your job, is to try to make all of those differences different if I go seven three one nine five then we have 4 & 8 & 6 & 4. Oh wait no this is still a disaster I wonder if this is even possible to solve this at your you’re okay to fail but I I’m supposed to be succeeding here okay um let’s go 9 1 No, maybe I’m gonna put the 7 up Here and the 5 here and a 3 here does this work Yeah yeah yeah yeah this looks good so this is nine minus one that’s eight seven minus one six four and two We’re all different we are successful we get to ride the end So this is part of an unsolved problem from 1967 called the graceful tree conjecture but it belongs in every elementary school’s curriculum, whenever they’re learning subtraction so the general problem is given any number of connected circles so they have to be connected any number that you want they have to be connected and there can be no loops so this would be a fine Insectoid to solve let me show you a loop so you could ask can this be solved so this might be solvable it might not But it’s certainly not the graceful tree conjecture the graceful tree conjecture means that there’s no loops, okay? okay, but why don’t we try to solve this so now we need 1 3 5 7 & 9 in 2 & 2 here can this be solved Consider how many even numbers you can get what’s the biggest even number that you can get as a difference between these right 8 yeah 9 and 1 the biggest you can get is 8 what’s the second biggest number that you can get 6 yes and The third biggest number 4 and then the last one is 2 there are only 4 different numbers that you can have but how many lines do we have to satisfy we have got 5 lines we’ve only got 4 even numbers to distribute between these five lines So no matter how you distribute these odd numbers You are always going to end up with a duplicate so here we have 8 6 4 2 & 4 again We’ve ended up with a duplicate over here so this starfish Cannot be solved it will fail every time if we have n circles and n lines connecting them We will never be able to solve that we can potentially solve for M circles in this case 5 circles and n minus 1 Maximum of four lines, we? Sometimes can solve for that so five circles where you you could solve it so here’s a butterfly There are five lines and one less connector so this could be solved what about this Five circles and four connectors I don’t know if this can be solved but this might be able to be solved the graceful tree Conjecture doesn’t include loops but this is still an Interesting question I I don’t know the solution to this so the graceful tree conjecture is one where you have all of your circles connected So you don’t have an outlier here and there’s no loops So that is guaranteed if you’ve got n circles you’re going to have n minus 1 connectors so here we’ve got 1 2 3 4 5 6 7 circles 1 2 3 4 5 6 lines and this is what is unsolved whether 4 n circles and n minus 1 lines Where there are no loops Can you always put in there odd? consecutive integers such that the difference between all connected circles all of those differences Are different what’s it’s not proven for that surely you mean for old designs of three oh yeah for all insectoids or all trees that you would care to design so this one for seven has been solved this is an example of Seven circles and six connecting lines there are actually 11 different ways that you can do that so here we have the 11 different ways to have seven circles all connected no loops What is unsolved is? going for more circles if you go into 30 or 40 circles Are these all solvable this has been an open conjecture since 1967 so presumably God if I start having more circles like 30 circles of 40 per calls the number of insectoids possible must just get metal it explodes Exactly right up to what number of circles is it solved for there are individual cases that have been solved for example I can put Circle in the middle and I can add any number of Circles on the outside that you want and this is always solvable and I can prove that quite easily I can put a 1 in the middle then I can go 3 5 7 9 11 13 15 17 19 21 23 And you can imagine I can keep on going here and this is always solvable because these differences are always different I could also put The largest number in the middle 23 could go in the middle and then I could distribute The other numbers all around all we solvable another example of a species that is always solvable are Snakes so you could imagine a snake of any length that you want and these are always solvable you might want to try this you can start with one and then you can go to your largest one I’m actually going to just skip I’m gonna go 1 3 5 7 and then I’m gonna come back 9 11 13 here, we have a difference of 12 a difference of 10 a difference of 8 a difference of 6 a difference of 4 and a difference of 2 All snakes can be solvable just by replicating that pattern there’s lots of species out there Not everything is a snake not everything is a sea star There’s lots of species out there you could very easily create and explore new species for example what happens if we have Something crazy that you know to sea stars joined with the long dendritic chain So is that solvable you can imagine that these can get very very complex very very quickly and Most species by the time you get to 40 circles most of those insectoids Very difficult to solve so presumably good if this is still an unanswered question That means there’s yet to be a species of tree found that is definitely Unsolvable because that would that would ruin it that’s correct We have not found an example that doesn’t work but that doesn’t mean that it doesn’t exist there are plenty of mathematicians who believe that that tree Exists that that there is a tree out there that cannot be solved would you be happy or sad if one was found oh I would be thrilled if one was find because I do this with my elementary school kids and after a week of them struggling to find one that can’t be solved I would love to say and Here, we have but it feels like it feels like nature is telling us they can always be solved like it feels like a Beautiful thing they’re also about it feels like it would break something beautiful Well it’s already broken like if you look beyond the graceful tree conjecture to allowing loops so here we have seven circles Six connectors so these ones cannot be solved so in a way it’s already broken but it’s interesting which Species work which species fail I like that I sort of see them as abominations and therefore they should It’s fair enough that they can’t be solved but there’s something perfect about the tree that has no loops and no islands Well that that’s where the crux is well where does a dividing line between Species that are always solvable and species that aren’t that’s what becomes interesting Are, you right are all of the trees really beautiful, well we’ll have to wait and find out

I get that putting odd numbers on the vertices and even numbers on the edges makes everything easy to follow and pleasing to look at, but wouldn't the question be easier to state if the nth odd number were replaced with n?

So how do I relate this to the real world?

I'm sure it's just my feeble human brain missing something important, but this all seems very arbitrary to me.

Who's conjecture is this and when was it made?

Juplicate.

What a random problem to focus on. It’s like you’re going out of your way to come up with a “problem” that is pointless and silly.

He talks about this as if lots of people really study this?

Does anyone know of programming guides that teach you to work with graphical nodes like this? I think It'd be fun writing a program to work these out and print out the results in a terminal looking like 6:03. For example, the Collatz conjecture is pretty straightforward to write.

7:06

"You could imagine a snake of any length you want."

mmmmmmmm

This conjecture in relation to chaos theory is really cool concept

Thanks for filming a better communicator than usual. The more geeky ones can be interesting, but this guy not only understands the material, he's skilful at delivering it too.

2:26

"and there can be no loops"

but

bröther may i have some lööpsSomeone needs a hobby

8:02 made me think. It feels like it should be possible to prove something like, “if you connect two solvable graphs together, the result will always be solvable” or something so that at the very least, a sea star connected to a normal snake can be shown to be solvable. Has anyone tried exploring something like that?

Why is this called the Graceful Tree problem and not the Graceful Insect problem?

Hi.

Many mathematicians have never been outside and so do not know what ants or starfish look like.

For every like this comment receives we can provide a mathematician with essential daylight. Thank you for your support.

"You're okay to fail, but I'm supposed to be succeeding here." 1:25

What is the significance of using consecutive

oddintegers? Surely the problem is the same if you just consider consecutive integers, since the differences are all even.On 6:18 there is a lonely circle without any edge- invalid.

Cool ideas but please can you introduce some actual mathematical definitions and terminology such as weights, connected graphs etc

Just an idea

So why does it have to be odd numbers? Every odd number is 2n+1, so differences between two are (2n+1)-(2m+1)=(2n-2m)=2(n-m). Wel'll always have even differences. But if we just used consecutive numbers, we could use "normal" numbers n (actually n+1 to be comparable) and the problem would be the same, or am I missing something here?

Ze body of ze ant iz zivized into zree zectionz…

This guy's voice is so much similar to the FBI guy from Wolf of wall street

Why use only odd numbers? The problem is exactly the same with numbers from 1 to n, instead of odd numbers from 1 to (2n–1)…

Its either this or subscribe to Pewdipie. Life of an 9 year old is hard.

If anyone's curious, this conjecture has been confirmed for all trees with up to 35 vertices by the Graceful Tree Verification Project.

Why is this important?

Most importantly, why are mathematicians wasting their time on these kinds of problems instead of cracking the Riemann hypothesis?

Thanks for these videos and making math fun for us folks who never took the time to explore the beautiful problems of the world!

Thumbs down again for supporting Patreon, the Dolores Umbridge of the Internet.

Interesting

Them circled tho

Can you do a video about the following problem? Suppose ACBD is a parallelogram with side lengths AB=3, and AD=2, and angle DAB = 60 degrees. Find the area of the parallelogram formed by the intersections of the internal bisectors of angle DAB, angle ABC, angle BCD, and angle CDA.

The professor has a nice voice

Ok but seriously why just use odd numbers? Using natural numbers in general should work…

"Not everything is a snake."

SOURCE??

Just an interesting observation: if we imagine that the circles are all carbon atoms, and the connectors are C-C bonds, every ring or cyclic arrangement has unsaturation≥1, so C-C bonds are more than the number of carbon atoms

6:18 – 3rd row, 4th circle – not a valid one, it's isolated.

Does someone know if every tree is Entirely Graceful (EG), so that you can put first number on any vertex ? I could not find any counter-example for many size 10 trees.

If yes then it is easy to go from a size N, EG Tree to any N+1 graceful tree by adding the N+1 vertex to the first vertex (number 0 if any number is used or 1 if only odd numbers).

Then if you can prove this new tree is not only graceful but Entirely Graceful, you get a proof a the graceful tree conjecture. Outer edges is easy, inner ones I have no idea.

What's up with using only odd numbers? Wouldn't it work exactly the same with integers?

I have a truly marvelous proof, which this comment is too small to contain.

I wonder where the problem is of proving by induction that you can always add another circle anywhere that works.

In these videos there is a lot of stating a theorem or a conjecture as "if a" and then a lengthy discourse on examples that do not satisfy condition "a". So it takes five minutes of seemingly infinite tedium to get to the "then b". In a fair world the instructor would say "the conjecture (or theorem i.e. a former conjecture since proven) is 'if a then b'" and THEN get into cases that don't fit within "a" or "b". When you say "and provided there are no loops" then you don't need to spend two days showing us what "no loops" does mean or might mean.

Ant?

there alot of things i would thought first but not an Ant. and i have subed to Ants Canada

It will be interesting to know if there was a spike in engagement at the timecode linked in the Bandersnatch show notes.

All "SUCCESSFUL" ants:

(antenna-1,antenna-2)–body1–body2–body3

(3,5)–7–1–9

(1,3)–9–5–7

(3,7)–1–9–5

(3,7)–9–1–5

(7,9)–1–5–3

(5,7)–3–9–1

I 've an unwanted unrequested comment : how could mathematicians use the result of the prove of that conjecture refusal or approval in some way that helps them to solve other things

Wow!!!!!

What is this guy's accent? American-Scottish?

Why can't you use negative e numbers? Like 1-9 or 3 – 5?

I like the sound effects.

You know what i found, you cannot

not solvethe sea-star ever.Well, i would just take two circles and connect them, since there wouldn't be another line of difference to compare to, the difference between the differences (sounds meta) would be undefined and hence the question unsolved.

I've already solved this problem

This seems like something that could be solved with a somewhat elegant proof…one would posit that all large graphs are constructed of solvable smaller graphs afterall…but Idk maybe that was the original conjecture.

Somebody make an algorithm

Nice.

6.9K likes

This reminds me of chain isomers in chemistry

@6:18 the circle on the 3rd row from the top and 4th column from the left is not connected to the overall structure, this is not a legal configuration.

4:30 Can't be done.

But isn’t any graveful tree a combination of “stars” and “snakes”?

i love this channel, you got to the point of the video in less than 30 seconds. most people take at lease 10 minutes

This guy seems like a really, really annoying, arrogant, self-important asshole.

Is there any software tool or computer program to do graceful labeling of a graph???

A loop is a connection from a vertex to itself. He meant a graph cycle 😛

I don't get this odd/even number thing. Can't you just do consecutive numbers? Shouldn't the problem be aquivalent?

I guess this form here might be chosen because you get different numbers at all circles AND vertices combined. But if the requirement was just to have different numbers at the vertices, consectutive numbers would suffice… right? Or am I missing something here?

His accent comes through when he says "found" and "out".

0:10 "well yeah"

In his head:

excuse me what the fI think brute force is a bit wasteful…. why don't we do a proof of contradiction by reducing it into subsections of solved shapes and processes to link them without creating any duplicates, we might be able to either prove by induction that it's impossible to make a shape that isn't solvable, or prove by contradiction that there must be a shape that isn't solvable

'Brady, what is this?'

ah shit here we go again6:15

This has an answer, sort of. Computers have been used to prove all trees up to a size of 35 circles are solvable.

How are there unsolved problems in 2019 with computers and smart people 😩

I want to watch more of this guy.

Are dartboards only solvable by putting the highest , or the lowest , number in the Middle ? (which should give a general proof , with n numbers attached one at a time to the next odd number could be interesting – that can only work if the second highest number is in the middle and the highest as an odd external attached to probably the lowest number. If all snakes can be solved using the low to midpoint reveresed run highest remaining to lowest then other forms can be moddeld into dartboard or snake ?

did this problem come up for a reason or did someone just think of it. it seems kind of arbitrary

He says that the number of trees with n nodes explodes: the sequence is OEIS A000055 for anyone interested.

Gordon: Ok, so, this is an example of a failure.

0:55

drops his penMe:

Ok, so, this is an example of a failure.This guy is a little too hung up on his animal analogy.

Wow I said the same numbers in the same order

At 6:18 there is an unconnected circle 4 from the left in the third row 😉

"We're successful. We get to ride the ant."

Exactly who believed that that would be a reward?

Does the shape of the tree matter?

Thumbs up on the Honey I Shrunk the Kids ant sounds.

I'm an example of a failure to!

But they did find one that definitely can't be solved

It's the pentagram!

The problem is that as soon as they find an unsolvable one, they define the problem so that it can't be that

Oh this is much information for my brain :v

Why do they take consecutive odd integers and not just integers?

No one:

Gordon:

hAuWBruh

Step 1: See the video. Step 2: Read the comments. Step 3: Laugh.

Follows instructions he's given, but doesn't know the rest of the problem. "Epic failure."

Knows what he's doing…fails with literally the same two sets of numbers…

Isn't that same as Kirby-Paris theorem?

The graceful espallier tree.

I have two questions

1. What's the highest number of circles for which all permutations have been solved?

2. What's the highest number of circles for which a non-standard permutation has been solved?

How would you go about it? Do you have any idea?

Solving a puzzle with a loop might be fun to solve.

Why do they specify consecutive odd numbers? Wouldn't it hold for any consecutive numbers if it holds for consecutive odd numbers, or is there a rule that no branch and circle can hold the same number, which forces the odd digits to be in all the circles?

Ask Matt Parker to come up with something that works and the end product will be a counterexample that almost works.

These tree sequence patterns can be done with any counting whole number counting series. (3-4 – 3 or 200s) as long the tree spits or is a train. These differences are sequential so you should be able to place the differences first and then place the point value. N points must be a greater N connection,

I wonder who will be the second Person to figure this out 😀 Euler already did it! 😀

I was hoping a giant ant would walk into the room at 2:00 and the rest of the video was uncomfortably quiet with them just riding atop the ant as it wandered slowly through the city.