Guichard-Combinatorics-Graph-Theory · Problem 5.8.1

Graph Theory

Mathematics — Probability · graph-coloring

Problem

Suppose

G

has

n

vertices and chromatic number

k

. Prove that

G

has at least

\binom{k}{2}

edges.