Due April 18

This problem is called an enumeration problem. We consider this to be a very hard problem, worth 25 points. Part credit is possible so have a try. Send answers and questions to mathstat@uoguelph.ca

The left hand picture below is called a triangle graph, made of three vertices connected by three edges. A graph is properly colored if the vertices at the ends of every edge are different colors. If we properly color the triangle in some number n of colors then there are n choices for the first color, n-1 choices for the second color, and n-2 choices for the third color. Since independent choices multiply there are n(n-1)(n-2) ways to properly color the triangle in n colors. Your problem: find the number of ways to properly color the square graph, pictured on the right below. Since all the colors do not have to be different to achieve a proper coloring the simple argument for the triangle won't quite work.

Send your answer to mathstat@uoguelph.ca

Back to Problems