Q5

Question 5 (15 Points): Graph Coloring. (01,03) Recall that a proper vertex coloring is an assignment of a color to each vertex in a graph such that adjacent vertices receive different colors. a) (5 points) Show that the Petersen graph (see below) has a vertex coloring with 4 colors. 3 b) (10 points) An umbrella Un is a simple undirected graph consisting of n + 1 vertices, where n vertices are connected into a line and a top vertex is adjacent to all of them. An example U4 is shown below. U4 How many ways are there to color U. with k colors? (n and & are two generic integers larger or equal to 2.)