THE EDGE CHROMATIC NUMBER OF A GRAPH

Introduction
This third game in the Colorful Mathematics series also deals with graphs, but presents a variation on the concept of the previous game.

To review, a graph is a group of circles ("vertices") some of them connected by lines ("edges"). This time, the edges must be colored in such a way that those connected to a common vertex receive different colors. The smallest number of colors that can be used is now called the edge chromatic number of a graph. The goal of this game is for you to devise ingenious methods to try to get as close as possible to this number both with the sample graphs provided and any graph created by the player.

The concept of a graph is very important in mathematics and industries. For a simple example, imagine that in a hockey league, a few games remain to be played until the end of the season, each team playing at most once each day and at most once against any other team. Now think of teams as vertices and connect two of them by an edge if they have a game remaining to play against each other. Then we get a graph and the smallest number of days required to complete the season is nothing else but the edge chromatic number of the graph, the number of days left corresponding to the number of colors used, right?

Software
Here is how to download the software, together with some technical information.

How to play
Ten pages of six sample graphs are available, presented in increasing order of difficulty, and drawing tools are also provided for creating new graphs.

To play the game, you successively color the edges of your graph using the colors of your choice; the computer will immediately display a message if a mistake is made in the coloring. Once all the edges of the graph are colored, a simple algorithm programmed in the game will be used by the computer to check if it can do better, giving appropriate feedback adapted to the difficulty level.

 INFO: A quick explanation of the game and other commands. DRAW: The mode "VERTICES" will clear the drawing board to draw vertices on a new graph. The mode "EDGES" will let you add the edges on your graph, and you can come back to this mode at any time to add or remove edges on your graph. PAINT: In the mode "COLORS", ten colors are available to color the edges; they are selected by clicking the can of your choice. The mode "CLEAR" will remove all colors of the graph. UNDO: You can successively undo the last operations performed; for example, while coloring a graph, "UNDO" will remove the colors one by one in reverse order. GRAPHS: A set of six sample graphs are available for each of ten pages, presented in increasing levels of difficulty. SAVE: One graph, completed or in progress, can be saved for each sample graph provided. Use the keyboard to type a title. QUIT: Quit the game to return to the main menu.