Competition problem — Combinatorics

Library / /74 of 94

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:

A $k$ -clique of a graph is a set of $k$ vertices such that all pairs of vertices in the clique are adjacent. The clique number of a graph is the size of the largest clique in the graph. Does there exist a graph which has a clique number smaller than its chromatic number?

Solution

Solution:

Consider a graph with 5 vertices arranged in a circle, with each vertex connected to its two neighbors. If only two colors are used, it is impossible to alternate colors to avoid using the same color on two adjacent vertices, so the chromatic number is 3. Its clique number is 2, so we have found such a graph.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.