# Math for eight-year-olds: graph theory for kids!

This morning I had the pleasure to be a mathematical guest in my daughter’s third-grade class, full of inquisitive eight- and nine-year-old girls, and we had a wonderful interaction. Following up on my visit last year (math for seven-year-olds), I wanted to explore with them some elementary ideas in graph theory, which I view as mathematically rich, yet accessible to children.

My specific aim was for them to discover on their own the delightful surprise of the Euler characteristic for connected planar graphs.

We began with a simple example, counting together the number of vertices, edges and regions. For counting the regions, I emphasized that we count the “outside” region as one of the regions.

Then, I injected a little mystery by mentioning that Euler had discovered something peculiar about calculating $V-E+R$.  Could they find out what it was that he had noticed?

Each student had her own booklet and calculated the Euler characteristic for various small graphs, as I moved about the room helping out.

Eventually, the girls noticed the peculiar thing — they kept getting the number two as the outcome!  I heard them exclaim, why do we keep getting two?  They had found Euler’s delightful surprise!

The teachers also were very curious about it, and one of them said to me in amazement, “I really want to know why we always get two!”

With the students, I suggested that we try a few somewhat more unusual cases, to see how robust the always-two situation really was. But in these cases, we still got two as the result.

The girls made their own graphs and tested the hypothesis.

Eventually, of course, I managed to suggest some examples that do in fact test the always-two phenomenon, first by looking at disconnected graphs, and then by considering graphs drawn with crossing edges.

In this way, we were led to refine the $V-E+R=2$ hypothesis to the case of connected planar graphs.

Now, it was time for proof.  I was initially unsure whether I should actually give a proof, since these were just third-graders, after all, and I thought it might be too difficult for the students. But when the teachers had expressed their desire to know why, they had specifically encouraged me to give the argument, saying that even if some students didn’t follow it, there was still value merely in seeing that one can mount an argument like that.  Excellent teachers!

The idea of the proof is that $V-E+R=2$ is true at the start, in the case of a graph consisting of one vertex and no edges. Furthermore, it remains true when one adds one new vertex connected by one new edge, since the new vertex and new edge cancel out.  Also, it remains true when one carves out a new region from part of an old region with the addition of a single new edge, since in this case there is one new edge and one new region, and these also balance each other. Since any connected planar graph can be built up in this way by gradually adding new vertices and edges, this argument shows $V-E+R=2$ for any connected planar graph. This is a proof by mathematical induction on the size of the graph.

Next, we moved on to consider some three-dimensional solids and their surfaces.  With various polyhedra, and the girls were able to verify further instances of $V-E+R=2$.

The girls then drew their own solids and calculated the Euler characteristic.  I taught them how to draw a cube and several other solids pictured here; when the shape is more than just a simple cube, this can be a challenge for a child, but some of the children made some lovely solids:

In the end, each child had a nice little booklet to take home. The images above are taken from one of the students in the class.

What a great day!

You can find a kit of the booklet here:

See also the account of my previous visit: Math for seven-year-olds: graph coloring and Eulerian paths.

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

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.

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.

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.

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.

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.

An Eulerian circuit starts and ends at the same vertex, but an Eulerian path can start and end at different vertices.

We 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.)

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?

The final result: a booklet of fun graph problems!

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.

Finally, check out my new book: