-- 发布时间：10/5/2008 4:16:00 PM
-- [求助]请教大虾图论的一个问题
图论小册子71页 5.1.6：
若简单图G的色数x(G)=k,且删除G中任何顶点v后，x(G-v)<x(G)，则称图G是k-临界的
其中第三问要求证明：若G是k临界的，则G中每个顶点的度数至少为k-1。
书后面的参考答案是这样给的，其中有一个地方我不明白
用反证法。若存在顶点v,d(v)<=k-2, 要推出一个矛盾。设与v相邻的顶点为v1,v2,v3,...,vm (m<=k-2). 因为x(G)=k, 因而G是k-可着色的，用k种颜色给G着色。首先用k种颜色中尽量少的颜色给G-v着色，则v1,v2...vm最多用了m种颜色。于是k种颜色中至少还有两种颜色。。。（后面的部分就讨论这两种颜色给v着色的情况，引出与k-色图相矛盾的结论）
答案只讨论了与v相邻的m个顶点着色所用颜色的种数，而没有考虑G中与v不相邻的顶点的着色情况。这种讨论方法是不是隐含着这样一个前提：用给与v相邻的顶点着色的颜色一定可以给与v不相邻的顶点着色？可是我没有找到相应的定理或依据，还请大虾指点