西安电子科技大学店$6.6.2平面图的着色软件学院我们称图G-ui中所有着红色或黄色的结点集为红黄集。称G-u中所有着黑色或白色的结点集为黑白集。当deg(u)=5并且与u相邻得5个结点着上了5种不同的颜色时，有以下两种中情况：i)V,和V3属于红黄集导出的G的子图的两个不同的连通分支中，如图所示，将V,所在分图中的红、黄色对调，并不影响G-u1的着色。然后将结点U着上红色即可对图G进行正常着色。西安电子科技大学 §6.6.2 平面图的着色 软件学院