How Many Good Colorings?

Please comment your solutions, questions and remarks..

Suppose G is a graph in which each vertex has three neighbours, for example:

A three valent graph

Suppose we have three colors, red green and blue, with which we want to color the edges of the graph. For instance like this:

A three valent graph

Call such a coloring good if at each vertex either three different colors meet or only one color occures. Thus the coloring in the picture above is not good, but the following two are good:

A three valent graph

Show that the number of good colorings of G is [tex]3^n[/tex] for some [tex]n\in \mathbb{N}[/tex]

Level 3/5 (Maybe 4/5 or even 5/5 depending on your mathematical prerequisites.)

About Vadim Kulikov

For details see this
This entry was posted in Algebra, Combinatorics, Mathematics, Wednesday Problem. Bookmark the permalink.

Leave a Reply

Your email address will not be published.