Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits

Image (11)As a guest today in my daughter’s second-grade classroom, full of math-enthusiastic seven-and-eight-year-old girls, I led a mathematical investigation of graph coloring, chromatic numbers, map coloring and Eulerian paths and circuits. I brought in a pile of sample graphs I had prepared, and all the girls made up their own graphs and maps to challenge each other. By the end each child had compiled a mathematical “coloring book” containing the results of their explorations.  Let me tell you a little about what we did.

We began with vertex coloring, where one colors the vertices of a graph in such a way that adjacent vertices get different colors. We started with some easy examples, and then moved on to more complicated graphs, which they attacked.

Image (12)Image (13)

Image (14)Image (15)

The aim is to use the fewest number of colors, and the chromatic number of a graph is the smallest number of colors that suffice for a coloring.  The girls colored the graphs, and indicated the number of colors they used, and we talked as a group in several instances about why one needed to use that many colors.

Next, the girls paired off, each making a challenge graph for her partner, who colored it, and vice versa.

Image (16)Image (17)

Image (18)Map coloring, where one colors the countries on a map in such a way that adjacent countries get different colors, is of course closely related to graph coloring.

Image (20)The girls made their own maps to challenge each other, and then undertook to color those maps. We discussed the remarkable fact that four colors suffice to color any map. Image (19)

 

 

 

Image (28)-001

Next, we considered Eulerian paths and circuits, where one traces through all the edges of a graph without lifting one’s pencil and without retracing any edge more than once. We started off with some easy examples, but then considered more difficult cases. Image (29)

Image (28)-002An Eulerian circuit starts and ends at the same vertex, but an Eulerian path can start and end at different vertices.

Image (30)-001We discussed the fact that some graphs have no Eulerian path or circuit.  If there is a circuit, then every time you enter a vertex, you leave it on a fresh edge; and so there must be an even number of edges at each vertex.  With an Eulerian path, the starting and ending vertices (if distinct) will have odd degree, while all the other vertices will have even degree.

It is a remarkable fact that amongst connected finite graphs, those necessary conditions are also sufficient.  One can prove this by building up an Eulerian path or circuit (starting and ending at the two odd-degree nodes, if there are such);  every time one enters a new vertex, there will be an edge to leave on, and so one will not get stuck.  If some edges are missed, simply insert suitable detours to pick them up, and again it will all match up into a single path or circuit as desired.  (But we didn’t dwell much on this proof in the second-grade class.)

Image (31)Meanwhile, this was an excellent opportunity to talk about The Seven Bridges of Königsberg.  Is it possible to tour the city, while crossing each bridge exactly once?Image (31)-001

 

 

 

 

The final result: a booklet of fun graph problems!

Graph Coloring Booklet

The high point of the day occurred in the midst of our graph-coloring activity when one little girl came up to me and said, “I want to be a mathematician!”  What a delight!

Andrej Bauer has helped me to make available a kit of my original uncolored pages (see also post at Google+), if anyone should want to use them to make their own booklets.  Just print them out, copy double-sided (with correct orientation), and fold the pages to assemble into a booklet; a few staples can serve as a binding.

See also my followup question on MathOverflow, for the grown-ups, concerning the computational difficulty of producing hard-to-color maps and graphs.

38 thoughts on “Math for seven-year-olds: graph coloring, chromatic numbers, and Eulerian paths and circuits

  1. As a bit of practical advice, this was more than enough material for a one hour session. Indeed, one could easily fill an hour with just the coloring topics, saving the Eulerian paths and circuits, as well as the booklet assembly, for another session. We chose instead to leave some of the larger graphs for coloring later or at home, which I think would be good, especially if it leads to mathematical discussions at home. Another issue was that it was more complicated than I had expected to arrange for the kids to draw graphs and maps in each other’s booklets, and so some care should go into organizing this.

    • My 7yo daughter could understand a theorem stating that in any party there are always two kids with the same number of friends. The proof uses the pigeonhole hole principle which can be easily explained with a game where kids run around chairs and there are less chairs than kids and the kids should try to grab a chair when they hear a command.

  2. So beautiful!
    If mathematics was taught in this way the school would have been a thousand times more exciting…I always thought that the trick to keep the students engaged and interested is to give them interesting problem, opportunities to achieve results independently. imho..

    ps:I apologize for my bad english

    • Thanks very much! The students seemed to like it very much, and they were excited to continue working on it when time ran out.

  3. Thank you for coming in yesterday and providing IIAB with such a wonderful experience as they explored this investigation. It was so developmentally appropriate and exciting to watch how engaged they were.

  4. This is really fantastic. I am going to use this kit or some slight modification in our math circle next semester!

    • I’m glad to hear you liked it. I think it would work great for a math circle; let us know how it goes.

  5. Wow. I teach 5 year olds english in japan, part of our weekly work is math, i think ill adapt some of these to our work.

    Very nicely done :-)

    • Domo arigatou! (Watashi mo nihon de oshiemashita, demo suugaku o oshiemashita.) I think it would work great for five-year-olds. The combination of mathematical thinking with coloring activity makes it ideal for young kids. But truthfully, I think the activity is fun for basically any age, and many parents have told me that they enjoyed completing the booklet with their kids.

  6. This is wonderful material for a math circle! As an extension, you could also do chromatic numbers in 3D by using gumdrops and toothpicks. (I.e., a child can see that the chromatic number of a tetrahedron is 4 because it takes 4 different colors of gumdrops to build it if we follow the rule that every toothpick must have 2 different colors on its ends.)

    BTW, I have a blog with other great activities for a math circle for 7 year olds:
    http://1001mathproblems.blogspot.com

    • I’m glad you noticed. It is beautiful after all, and seven-year-olds can 3-color it, although they find it a challenge to do so.

  7. A friend shared this on Facebook, and as a former math teacher and later professor (and implicitly long-time math student) this is just the kind of thing that should be in the curriculum. It’s wonderful, and I’m going to bookmark this for when I get to guest lecture in my daughters’ math classes. (As an aside, I remember my father talking to my class about probability when I was in elementary school, and I wound up a mathematician, so good luck to your daughter).

  8. I have to admit being confused by the “4 colors suffice for any map” idea. Consider the Central African Republic, which is surrounded by 6 countries. Or Niger, or Uganda…

    • You could color the Central African Republic purple, say, and then go red-blue-red-blue-red-blue for the surrounding countries, handling the particular case of those countries with only three colors. You may have assumed that those other six countries must use more than three colors, but in fact you only needed two for them. The four-color theorem is a wonderful, deep theorem with a rich history, which is also connected with philosophical ideas surrounding the question of what does it mean to prove something, for the simplest proofs were carried out first by computer, and led to truly enormous proof objects that could not really be checked by a human. See http://en.wikipedia.org/wiki/Four_color_theorem.

  9. This is perfect. I am a HS math teacher with young kids. I am doing “math camp” this summer and enjoying this activity.

  10. beautiful. Something intrigues me a lot: is there a collection of such exercises that could supplement (or ideally replace) a “normal” school curriculum, for most ages besides 8 year olds, such that these children learn and develop their math skills (and much more than that) in this beautiful way?
    If there isn’t such collection compiled yet, can it be created? I can just imagine the benefits this would bring to the many children that will have the freedom and pleasure to use it.
    Let’s build something like this!

  11. Pingback: Somewhere else, part 142 | Freakonometrics

  12. Hello, and congrats for this wonderful kit ! Do you have an objection if I translate it in French for my kids + put it on my blog with of course your refs and links ? Thanks :)

  13. This is a wonderful booklet indeed! I particularly like that in the last page, the mathematical terminology on the right side, including the reason why the answer is “no”, becomes self explanatory to any age, after reading the left side. I will translate this to Greek, German, and Spanish if that’s ok. I believe it’s terribly important to make maths interesting and fun to all ages!

  14. The graph-coloring activity worked very well with my own second grade math circle. The kids explored and noticed many interesting things, such as that a triangle has a chromatic number of 3, so any graph with an embedded triangle must need at least 3 colors. We also did some word problem applications. (E.g., You are planning a dinner party where certain people don’t get along, and you have to find the minimum number of tables you must use so that every arguing couple is separated.)
    It also inspired me to find a way to do more topology with 7-year-olds. Here’s my Euler’s formula activity: http://1001mathproblems.blogspot.com/2014/07/this-weeks-puzzle.html. The trick was to find a way to ask questions so that the children are exploring the relationships and not simply learning a formula.
    Thanks again for your wonderful contribution!

  15. I have taught the seven bridges of Konigsberg to Year 10 and they seemed to find it flat and boring. I think its the way it is presented within a time poor setting, and you end up teaching formulas. I think that starting with this simple colouring approach would be a lot more fun.
    I think I would change the writing to sentence case, because some children start to copy the upper case style, then get mixed up with their writing in later years.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>