Question: Show that the coloring produced by this algorithm may use more colors than are necessary to color a graph. A connected graph G is called chromatically k-critical if the chromatic number of G is k, but for every edge of G, the chromatic number of the graph obtained by deleting this edge from G is k - 1.