HMMT 二月 2009 · TEAM2 赛 · 第 6 题

英文解析

6. (a) [ 5 ] If a single vertex (and all its incident edges) is removed from a finite graph, showthat the graph’s chromatic number cannot decrease by more than 1.
   Solution: Suppose the chromatic number of the graph was C , and removing a singlevertex resulted in a graph with chromatic number at most C − 2. Then we can color theremaining graph with at most C − 2 colors. Replacing the vertex and its edges, we canthen choose any color not already used to form a coloring of the original graph using atmost C − 1 colors, contradicting the fact that C is the chromatic number of the graph.
   (b) [ 15 ] Show that, for any n > 2, there are infinitely many graphs with chromatic numbern such that removing any vertex (and all its incident edges) from the graph decreasesits chromatic number.
   Solution: Let k > 0 be an odd number, and let G be a graph with k vertices arrangedin a circle, with each vertex connected to its two neighbors. If n = 3, these graphs can be arbitrarily large, and are the graphs we need. If n > 3, let H be a complete graphon n − 3 vertices, and let J be the graph created by adding an edge from every vertexin G to every vertex in H . Then n − 3 colors are needed to color H and another 3 areneeded to color G , so n colors is both necessary and sufficient for a good coloring of J .
   Now, say a vertex is removed from J . There are two cases:
   If the vertex was removed from G , then the remaining vertices in G can be colored with
   2 colors, because the cycle has been broken. A set of n − 3 different colors can be usedto color H , so only n − 1 colors are needed to color the reduced graph. On the otherhand, if the vertex was removed from H , then n − 4 colors are used to color H and 3
   used to color G . So removing any vertex decreases the chromatic number of J . 2