Reference no: EM131186928

A three coloring of a graph labels each vertex v with one of three colors, say R, B or G, so that the two end points of any edge have different colors. Consider an undirected graph which is a single path, i.e.,where the vertices are v1...vn, and there is an edge between each vi and vi+1 for i = 1..n-1. How many 3 colorings does this graph have? (2 points correct answer. 1 point short explanation). How many bits are required to describe such a 3-coloring? (2 points correct answer, 1 point short explanation) Give coding and decoding algorithms that given the 3-coloring, outputs a string of the length above that codes it, and given the code, outputs the original 3-coloring. (3 points algorithm description, 1 point short explanation).