Grinberg-Introduction-Graph-Theory · Problem 6.7

Colorings

Mathematics — Graph Theory · proper-colorings-edge-count

Problem

Let

k \in \mathbb{N}

. Let

G

be a simple graph with fewer than

\dfrac{k(k+1)}{2}

edges. Prove that

G

has a proper

k

-coloring.