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, n1
choices for the second color, and n2 choices for the third
color. Since independent choices multiply there
are n(n1)(n2) 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
