HMMT 二月 2009 · TEAM1 赛 · 第 5 题

英文解析

5. The size of a finite graph is the number of vertices in the graph.
   (a) [ 15 ] Show that, for any n > 2, and any positive integer N , there are finite graphs withsize at least N and with chromatic number n such that removing any vertex (and all itsincident edges) from the graph decreases its chromatic number.
   Solution: Let k > 1 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 .2
   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 .
   (b) [ 15 ] Show that, for any positive integers n and r , there exists a positive integer N suchthat for any finite graph having size at least N and chromatic number equal to n , itis possible to remove r vertices (and all their incident edges) in such a way that theremaining vertices form a graph with chromatic number at least n − 1.
   Solution: We claim that N = nr is large enough. Take a graph with at least nrvertices and chromatic number n , and take a good n -coloring of the graph. Then by
   Pigeonhole, at least r of the vertices are the same color, which means that no pair ofthese r vertices is adjacent.
   Remove this r vertices. If the resulting graph can be colored with only n − 2 colors, thenwe can add the r vertices back in and color them with a new ( n − 1)st color, creating agood coloring of the graph with only n − 1 colors. Since the original graph has chromaticnumber n , it must be impossible to color the smaller graph with n − 2 colors, so we haveremoved r vertices without decreasing the chromatic number by 2 or more.