TEACHER'S CORNER

Introduction
The aim of Colorful Mathematics is to help students experience a mathematical problem and, through a game-oriented approach, come to understand its difficulties and partial solutions. Each of the five games deals with contemporary problems that are still the subject of active research by mathematicians, computer scientists and industry researchers.

Colorful Mathematics has transformed these problems into coloring games that can be presented to students throughout the range of K-12 grade levels. Each of the five games provides ten pages of sample graphs presented in increasing levels of difficulty. It is strongly encouraged as well that students create new graphs on their own to test ideas of their own, as this process is an important part of mathematical reasoning.


Details on the games
You might find it helpful to print this page as a resource for a class activity.

In all of the games, boxes and banners display messages to the student with the feedback appropriate to decisions they have made in that game and adapted to the difficulty level.

In the four games that require the drawing of a graph (by drawing vertices and edges), there are limitations to the kind of graphs that can be drawn. First of all, the number of vertices is limited by the size of the screen. Also, if three vertices are drawn in a straight line, the first and third cannot be connected to each other by an edge. This capability was sacrificed to ensure a clear display of the graph, while still leaving enough variety to play with the problem.




The Four Color Map Problem

This game is based on the "Four Color Theorem", which states that four colors are sufficient to color any map so that regions sharing a common border receive different colors. The goal of this game is not for students to prove this, but rather to experience the idea; to draw maps and devise methods to color them with the fewest possible number of colors. Sometimes two or three colors will suffice, but more often four are necessary. However, using only four colors is not as straightforward as it may appear so six colors have been provided which should make it relatively easy for everyone to color their maps correctly. The more adventurous will reduce this number to five, or even better to four.

The sample maps begin with a page of simple pictures for warm-ups or for younger students, a page of more abstract mathematical patterns, a third of "traditional" maps such as Canada, USA, Europe, Africa, South America and Asia, and a succession of seven more pages of increasingly challenging patterns. The blank spaces forming the right hand column on each page are for newly drawn maps (by the students) to be saved.

The computer will display messages to let the student know if two neighboring regions have been colored with the same color or when the map is completed by counting the number of colors used. A shaded banner will appear at the top of the screen when the computer is checking the maps; depending on the size of the colored region and the speed of the computer, this might take a few seconds. This evaluation is intentionally not too strict, to keep the game from becoming too "picky" and to allow for some short borders; for example, two countries who are sharing only a corner are not in practice considered to be sharing a common border.

After having completely colored a map, a message will appear on the screen asking the student to try to improve on the number of colors required, or to be able to show that this number cannot be reduced. More advanced students, for example, should be able to verify that two or three colors are in general not enough to color their map.

Here is a sample of questions for discussion with the curious student:

  1. Can you recognize maps that require only two colors?
  2. Can you recognize maps that require only three colors?
  3. Can you recognize maps that necessarily require four colors?
  4. Do you have a good method to color a map with just five colors? Four colors?
  5. Can you express this as an algorithm?



The Chromatic Number of a Graph

Once again, the goal of each of these games in the Colorful Mathematics series is to help develop the skills involved in the process of mathematical or scientific reasoning: that is, to experience a problem and come to understand its difficulties and partial solutions. In the case of the real problem of computing the chromatic number of a graph, no efficient algorithm has yet been found. Finding the chromatic number of a graph is indeed a very difficult problem even for today's most powerful computers. Here, only a simple and quick algorithm is used, but even so to tie the computer is a substantial achievement and it is also possible to beat it! The student is strongly encouraged to try to equal and in fact, perhaps better the computer's assessment, as it is precisely this creative, original thinking that is truly at the heart of mathematical reasoning.

The computer feedback programmed for this game specifically involves the following: the computer will check the graph after each coloring and will warn the user if the same coloring was used for two connected vertices. The computer also verifies if the graph is completed and counts the number of colors used, then uses its own simple algorithm on the graph and checks if it can do better. Finally, appropriate messages will be displayed, based on the difficulty level.

Here is a sample of questions for discussion with the curious student:

  1. Can you recognize graphs that require only two colors? Three colors?
  2. Can you draw a graph that will necessarily require 5 colors? 11?
  3. Do you have a good method to color your graphs? A fast method?
  4. Can you guess how the computer algorithm works?
  5. Can you improve on the computer algorithm? Write your own?



The Edge Chromatic Number of a Graph

This game is similar to the preceeding one, but in this case the edges are colored and it is the edges connected to a common vertex that must receive different colors. You will notice that the type of feedback from the computer is similar between the two games as well. Specifically, the computer will restrict the coloring by letting the player know if two edges connected to a common vertex have been colored with the same color. When the coloring of the graph is completed, the computer will check if it can do better and then display related messages, based on the difficulty level.

It is easier here to draw a graph that necessarily uses more than ten colors (although only ten colors are provided as a reasonable supply). For example, if eleven edges are connected to a common vertex, at least eleven colors will be needed. However we feel that there is plenty of room left to draw very complex graphs.

Here are some sample questions for discussion with the curious student:

  1. Can you recognize graphs that require only two colors?
  2. Can you draw a graph that will necessarily require 11 colors? 55?
  3. Do you have a good method to color your graphs?
  4. Can you guess how the computer algorithm works?
  5. Can you improve on the computer algorithm? Write your own?
  6. Are "The Edge Chromatic Number of a Graph" and "The Chromatic Number of a Graph" really the same problem? Can an algorithm for one problem be modified to solve the other problem?



The Two-Player Chromatic Number of a Graph

As with the chromatic number, the goal of this game is to color the vertices of a graph with the smallest possible number of colors, such that two vertices connected by an edge receive different colors. Here, however, we must choose in advance the maximum number of colors that will be allowed in the game, and we color the vertices alternately with another player, in this case the computer. In practice, the other player will try to force as many colors as possible; the student must be clever to minimize this number. The smallest possible number of colors which will allow the first player to always win that graph (using only that number of colors) is called the two-player chromatic number of the graph. This number is always at least as big as the chromatic number of the graph, but often much larger.

The computer will first ask the student to select the maximum number of colors allowed for that game, then the student begins to color the graph alternately with the computer. After each coloring, the computer will check if two vertices connected by an edge have received the same color and will inform the student. If, however, all is correct, the computer will take its turn, trying to force an extra color. The student succeeding to color the entire graph with the number of colors fixed at the beginning wins the game, otherwise the computer wins. The goal is thus to fix at the start the smallest number of colors which ensures a win for the first player, regardless of the strategy of the opponent.

Here is a sample of questions for discussion with the curious student:

  1. Can you recognize graphs that require only two colors? Three colors?
  2. Can you draw a graph that will necessarily require 5 colors? 11?
  3. Do you have a good method to color your graphs? A fast method?
  4. Can you guess how the computer algorithm works?
  5. Can you improve on the computer algorithm? Write your own?
  6. What is the relationship between the chromatic number and the two-player chromatic number of a graph?



The Dominating Number of a Graph

The use of one color to select some vertices in a graph so that every vertex is either colored or connected by an edge to a colored one creates a dominating set of a graph. While the goal of this game is to obtain a dominating set of the smallest possible size (the dominating number), it is likely that more vertices than necessary will be colored. The feedback from the computer to the player has been designed with this in mind. In fact, this game is different from the others in this series in that there are no restrictions on which vertices to color. Messages will be displayed only when a dominating set has been reached, although that does not necessarily mean that the smallest dominating number has been reached!

Here are some sample questions for discussion with the curious student:

  1. Can you draw a graph that has a dominating set with only one vertex? Two vertices?
  2. Can you draw a graph that necessarily requires a large dominating set?
  3. Do you have a good method to find a small dominating set?
  4. Can you guess how the computer algorithm works?
  5. Can you improve on the computer algorithm? Write your own?


Terminology

Map
We all know the familiar notion of a geographical map. Here, we loosely use the notion of map to denote any regions that we can draw, and border to mean any common separating line.

The "Four Color Theorem"
It took over a hundred years for mathematicians to prove that four colors were sufficient to color a map, no matter how complicated, so that regions sharing a common border receive different colors. This was verified or proved, as we say in mathematics, by K. Appel and W. Haken in 1976 making substantial use of the computer to classify thousands of configurations. An interesting account of their story is available in the popular science magazine "Scientific American", October 1977.

Graph
A graph is a bunch of circles joined by lines; we call these circles "vertices" and the lines "edges".

Chromatic number of a graph
The smallest number of colors used to color the vertices with the only restriction being that those joined by an edge receive different colors.

Edge chromatic number of a graph
The smallest number of colors used to color the edges with the only restriction being that two edges connected to a common vertex receive different colors.

Two-player chromatic number of a graph
The smallest number of colors that can be used to alternatively color the vertices with anyone else in such a way that two vertices joined by an edge must receive different colors. This number is at least as large as the chromatic number of the graph, and usually much bigger.

Dominating set of a graph
A collection of vertices in the graph, such that every vertex is either in the collection, or joined by an edge to a vertex in that collection. Notice that there can be many dominating sets in a graph; the collection of all vertices is certainly an example.

Dominating number of a graph
The smallest size of a dominating set in the graph. In our game, we select a dominating set by coloring its vertices blue.


COLORFUL MATHEMATICS

BACKGROUND

IS THIS REALLY MATHEMATICS?

THE GAMES

RELATED SITES