西安电子科技大学$6.6.1图着色的基本概念软件学院学教家教家家教家【定理】无向图G的色数（G)=2，当且仅当G是一个二部图。证明：若G是二部图，由于G中的结点集V可以划分为两个子集X和Y，且X和Y中的结点间均不邻接。这样，我们可以使用两种颜色，分别对X和Y中结点着色，即得到G的一种正常着色。所以G的色数等于2。若G的色数等于2，那么图G中至少有两个结点和一条边。若我们用A、B两种颜色对G进行正常着色，那么可以将着A的结点和着B的结点是图G的结点集合V的一个划分。并且A中结点内部不可能存在边，同理B中结点内部也不可能存在边。故G是二部图。西安电子科技大学 §6.6.1 图着色的基本概念 软件学院 证明：若G是二部图，由于G中的结点集V可以划分为两个子 集X和Y，且X和Y中的结点间均不邻接。这样，我们可以使 用两种颜色，分别对X和Y中结点着色，即得到G的一种正常 着色。所以G的色数等于2。 若G的色数等于2，那么图G中至少有两个结点和一条边。若 我们用A、B两种颜色对G进行正常着色，那么可以将着A的 结点和着B的结点是图G的结点集合V的一个划分。并且A中 结点内部不可能存在边，同理B中结点内部也不可能存在 边。故G是二部图