申論題

6. (15 points) If a graph G has chromatic number k, but every graph G' resulting from removing one cdge from G has chromatic number at most k–1. Is it always true that every vertex in G has degree at least k–1? Prove your answer. Recall that the chromatic number of a graph is the minimum number of colors required to color all vertices such that adjacent vertices have different colors.