In this video we prove by induction that every graph has chromatic number at most one more than the maximum degree. Odd cycles and complete graphs are examples for which the chromatic number meets this upper bound exactly. For other graphs, Brook's Theorem tells us that the chromatic number is at most the maximum degree. We will prove Brook's Theorem in a later video.
-- Bits of Graph Theory by Dr. Sarada Herke.
Related videos:
[ Ссылка ] - Graph Theory: 64. Vertex Colouring
[ Ссылка ] - Graph Theory: 65. 2-Chromatic Graphs
