(May 19, 2016)  This is a graph-theory story best told with pictures, so feel free to go straight to the photo gallery below.  But I’ll try to explain it in the words I used with the students:

Draw a tree.  Any Tree.  Sequentially number both ends of each branch or branch segment, starting with 1.  You have created a “graph” – each number is at a “vertex” and each branch segment is an “edge.”  For each edge (the segment between 2 adjacent vertices), calculate the positive difference between the adjacent vertex numbers, and label that edge with your result.  Your tree is “graceful” if you have an edge with every number beginning with 1 up to the number of edges your tree has, without repeats. 

Unsolved question:  Is every tree graceful?

The kids spent the whole hour exploring this question.  They drew their own trees, and tested them out.

Some of the interesting questions and comments that came up:

• “Why can’t I use the tree I drew for this problem?” J wanted her branches to reconnect to the tree in a way that I said was disallowed.  I explained that graphs can be “trees” or “nets” and that the Graceful Tree conjecture did not apply to nets.  Her trees were nets.  (See Gordon Rugg’s blog for a nice visual explanation of the difference between trees and nets.)
• “This is like Sudoku.” Wikipedia describes Sudoku as a “logic-based, combinatorial number-placement game.”  Yep, sounds the same!
• “This is like that problem we did with the names.” (Reference to “Finding a Planar Graph,” a graph theory problem we did in week 1.)
• Is there a strategy in how you construct your tree? (This question was from me.)

The students came up with multiple types of trees, so we briefly discussed categories of trees – caterpillar trees, star trees, etc.  – and what mathematicians have (or have not) determined about each.  Take a look at the photos of the kids’ attempts in the photo gallery.  If this question really captures your fancy, mathematician Shiva Kintali has done a lot of work on graceful trees – look him up on google and youtube (search “Kintali Graceful Tree”).

I urge you again, though, to check out the photos of the students’ work.

Rodi

PS  Thanks again to Gordon Hamilton, his website math pickle, and the Unsolved K-12 team, for introducing me to another wonderful unsolved problem in mathematics!

Graceful tree conjecture:  http://www.openproblemgarden.org/op/graceful_tree_conjecture, http://www.cs.princeton.edu/~kintali/papers/Matt_Superdock_Thesis.pdf

graph theory basics:  http://world.mathigon.org/Graph_Theory

[juicebox gallery_id=”133″]