HMMT 二月 2009 · TEAM1 赛 · 第 4 题

英文解析

4. A k-clique of a graph is a set of k vertices such that all pairs of vertices in the clique areadjacent.
   (a) [ 4 ] Find a graph with chromatic number 3 that does not contain any 3-cliques.
   Solution: Consider a graph with 5 vertices arranged in a circle, with each vertexconnected to its two neighbors. If only two colors are used, it is impossible to alternatecolors to avoid using the same color on two adjacent vertices, so the chromatic numberis 3.
   (b) [ 10 ] Prove that, for all n > 3, there exists a graph with chromatic number n that doesnot contain any n -cliques.
   Solution: We prove the claim by induction on n . The case n = 3 was adressed in (a).
   Let n ≥ 3 and suppose G is a graph with chromatic number n containing no n -cliques.
   ′
   We produce a graph G with chromatic number n + 1 containing no ( n + 1)-cliques asfollows. Add a vertex v to G , and add an edge from v to each vertex of G .
   To see this graph has chromatic number n + 1, observe that any coloring of the vertices
   ′
   of G restricts to a valid coloring of the vertices of G . So at least n distinct colors must be used among the vertices of G . In addition, another color must be used for v . By
   ′
   coloring v a new color, we have constructed a coloring of G having n + 1 colors.
   ′
   Lastly, any ( n +1)-clique in G must have at least n vertices in G which form an n -clique,
   ′
   which is impossible. Therefore, G has no ( n + 1)-cliques.