Amazing Mathematics Teaching Activity

from: jdh.hamkins.org

A mathematical investigation of graph coloring, chromatic numbers, map coloring and Eulerian paths and circuits. By the end each child will compile a mathematical “coloring book” containing the results of their explorations.

We begin with vertex coloring, where one colors the vertices of a graph in such a way that adjacent vertices get different colors. It starts with some easy examples, and then moves on to more complicated graphs.

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.

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.

Next, we consider 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.

You can discuss 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.

This is 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?

Read the full report: http://jdh.hamkins.org/math-for-seven-year-olds-graph-coloring-chromatic-numbers-eulerian-paths/

Get the resource: Andrej Bauer has assembled the images into a single pdf file: https://drive.google.com/file/d/0B7eG5PHUDcmZX1FnOHRhSU9ubUU/edit?usp=sharing, and filtered the color to black/white to improve printing.

Support it with an in class app: from the apple App Store OR One Touch Draw http://www.windowsphone.com/en-us/store/app/one-touch-draw/2c1b6ab4-d8c0-45f8-a2ac-b94fa721b39e

(Most amazingly…..this was a second grade class!!!)