图的着色问题图得顶点着色定义2图G得色数就是使G为n着色得数得最小值,图G得色数记为(G)、若(G)n,则称G就是n可着色得、若(G)=n,则称G就是n色得、定理1一个图就是可双色得当且仅当她没有奇数长得圈、定理2设=(G)为图G得顶点度得最大值,则G就是(+1)—可着色得、定理3(布鲁克斯定理)如果G就是一个连通图且不就是完全图也不就是奇数长得圈,则G就是(G)—可着色得、定理4每个平面图都就是6可着色得、4色猜想每个可平面图就是4—可着色得、10图得边着色对某些特殊类型得图,我们能容易确定她得边色数、例如:定理1如果p就是不为1得奇数,则(Kp)=p、如果p就是偶数,则(Kp)=p-1、Kp最多有(p-1)(Kp)/2条边;若p(≥4)就是偶数,则Kp-1中加一顶点v且v与Kp-1得每一顶点联结一条边而得到Kp、定理2如果G就是偶图,则(G)=(G),即偶图得边色数等于她得顶点得最大度、②、若不出现在u和不出现在v得颜色有如下特点: