The chromatic number of a graph is the minimum number of colours used in a…

Correct statements: the graph contains an independent set of size at least n/ k; the graph contains at least k(k − 1)/2 edges.

Reasoning:

• Independent set size at least n/k: In any proper k-colouring the vertex set is partitioned into k colour classes, each an independent set. By the pigeonhole principle at least one class has size at least n/k, so the graph contains an independent set of size ≥ n/k.

• Edge lower bound k(k−1)/2: Every k-chromatic graph contains a k-critical subgraph (removing any edge lowers the chromatic number). In a k-critical graph every vertex has degree at least k−1. Hence the sum of degrees is at least k(k−1), so the number of edges in that subgraph is at least k(k−1)/2. Therefore the original graph has at least k(k−1)/2 edges.

• Why a k-clique is not required: Chromatic number ≥ clique number, but equality need not hold. For example, the 5-cycle has chromatic number 3 but its largest clique has size 2, so a k-chromatic graph need not contain a complete subgraph on k vertices.

• Why a vertex of degree at least k is not guaranteed: From the k-critical subgraph argument we only get minimum degree ≥ k−1, not ≥ k. The 5-cycle (chromatic number 3) has every vertex of degree 2 = k−1, so degree ≥ k is not guaranteed.