发布网友 发布时间:2023-07-11 02:25
共2个回答
热心网友 时间:2024-12-10 06:14
该题结论中的充分性不成立,看图1中4点的图不是树,但却是2色的。就既使是连通图也不成立,看图2中的图,它也不是树,它也是2色的。
必要性成立,如果G是树,则一定着色数为2。
证明取树G的任意一点P,对树中所有结点按下面方式着色:如果结点与P的路径长为偶数,则该结点(包括P点)着某种颜色C1,如果结点与P的路径长为奇数,则该结点着另外一种颜色C2,如果此时有相邻的两点A,B着同一种颜色,不失一般性,设A,B着颜色C1,则P到A,B各有一条路径长为偶数的路,该路与AB边就构成了回路,这与G是树矛盾,故不可能有相邻的两点着同一种颜色,于是用C1,C2两种颜色对树G进行了正常着色,故G的着色数为2。
热心网友 时间:2024-12-10 06:15
不详...