西安电子科技大学店$6.6.1图着色的基本概念软件学院【定理】任何图G均满足(G)≤△(G)+1。证明：设图G中结点的最大度等于k，构造G的一个k十1种颜色的正常着色。对于图G中度数最大的结点V，由于它邻接的结点个数最大为k，若这k个结点均着上了不同的颜色，那么也可以用第k+1种颜色对V进行正常着色。西安电子科技大学 §6.6.1 图着色的基本概念 软件学院 证明：设图G中结点的最大度等于k，构造G的一个k＋1种 颜色的正常着色。 对于图G中度数最大的结点v，由于它邻接的结点个数最大为 k，若这k个结点均着上了不同的颜色，那么也可以用第k+1 种颜色对v进行正常着色