Competition problem — Combinatorics

Library / /23 of 94

Combinatorics Difficulty 4.5 AIME Prove it United States

Problem:

Let $G$ be a finite graph in which every vertex has degree $k$ . Prove that the chromatic number of $G$ is at most $k+1$ .

Solution

Solution:

We find a good coloring with $k+1$ colors. Order the vertices and color them one by one. Since each vertex has at most $k$ neighbors, one of the $k+1$ colors has not been used on a neighbor, so there is always a good color for that vertex. In fact, we have shown that any graph in which every vertex has degree at most $k$ can be colored with $k+1$ colors.

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.