**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 [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.)