Introduction to Graph Theory · Problem 6.7

Colorings — Darij Grinberg

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

Problem

Let k∈Nk \in \mathbb{N}. Let GG be a simple graph with fewer than k(k+1)2\dfrac{k(k+1)}{2} edges. Prove that GG has a proper kk-coloring.

Related theory

Browse the problem library