Combinatorics and Graph Theory · Problem 5.8.1

Graph Theory — David Guichard

Mathematics — Combinatorics · graph-coloring

Problem

Suppose

G

has

n

vertices and chromatic number

k

. Prove that

G

has at least

\binom{k}{2}

edges.