Coloring Applet

Unfortunately, your brouwser is unable to show Java applets.
How many colors are necessary to color the vertices (points) of this graph in such a way that adjacent vertices (i.e. points that are connected by a direct line) get different colors? Try it! As you will see, the computer won't allow you to cheat.

You may change graphs by clicking on the word "Graph i".

Can you explain for each of these graphs why it cannot be colored with fewer colors than you did?


Erich Prisner
August 2000.