HMMT 二月 2009 · TEAM2 赛 · 第 5 题

英文解析

5. [ 10 ] A k-clique of a graph is a set of k vertices such that all pairs of vertices in the clique areadjacent. The clique number of a graph is the size of the largest clique in the graph. Doesthere exist a graph which has a clique number smaller than its chromatic number?
   Solution: Consider a graph with 5 vertices arranged in a circle, with each vertex connectedto its two neighbors. If only two colors are used, it is impossible to alternate colors to avoidusing the same color on two adjacent vertices, so the chromatic number is 3. Its clique numberis 2, so we have found such a graph.