# 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:

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

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:

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

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