我们已经看到，对每个满足x(G)≤△(G+1的图G,等号在完全图和奇圈时 成立.对于其他情况，这个一般的界可以作少许的改进， 定理5.2.4(Brooks,1941)设G是一个连通图.如果G既不是完全图，也不 是奇圈，那么 x(G)≤△(G) 证明我们对G使用归纳法.如果△(G≤2，那么G是一条路或一个圈 结论显然成立.因此假设△：=△(G)≥3，并且结论对于顶点数较小的图都成立， 假设X(G△：止个人 设v是G的一个顶点，令H:=Gu,由归纳假设知，X(H)≤△，并且对H的 每个分支H'有X(H)≤△(H)≤△，除非H'是完全图或是奇圈，在这种情况下， 有X(H)=△(H)+1≤△，这是因为H印的每个顶点在中都具有最大度，并且 这样一个顶点和，在G中也是相邻的， 因为H可以△着色但G不能，所以我们有下面的结论： H的每个△-着色，在v的邻点使用了所有的颜色1，·，△. (1) 特别地，d(v)=△