Proof
Lovász (1975) gives a simplified proof of Brooks' theorem. If the graph is not biconnected, its biconnected components may be colored separately and then the colorings combined. If the graph has a vertex v with degree less than Δ, then a greedy coloring algorithm that colors vertices farther from v before closer ones uses at most Δ colors. Therefore, the most difficult case of the proof concerns biconnected Δ-regular graphs with Δ ≥ 3. In this case, Lovász shows that one can find a spanning tree such that two nonadjacent neighbors u and w of the root v are leaves in the tree. A greedy coloring starting from u and w and processing the remaining vertices of the spanning tree in bottom-up order, ending at v, uses at most Δ colors. For, when every vertex other than v is colored, it has an uncolored parent, so its already-colored neighbors cannot use up all the free colors, while at v the two neighbors u and w have equal colors so again a free color remains for v itself.
Read more about this topic: Brooks' Theorem
Famous quotes containing the word proof:
“O, popular applause! what heart of man
Is proof against thy sweet, seducing charms?”
—William Cowper (17311800)
“From whichever angle one looks at it, the application of racial theories remains a striking proof of the lowered demands of public opinion upon the purity of critical judgment.”
—Johan Huizinga (18721945)
“A short letter to a distant friend is, in my opinion, an insult like that of a slight bow or cursory salutationa proof of unwillingness to do much, even where there is a necessity of doing something.”
—Samuel Johnson (17091784)