对于最小顶次数为n的任意单图,证明：存在一种（n-1)边着色,使与图中每顶关联的边中有（n-1)种颜色.（n>1)我又不是留学生，我们的书又不是英文版的，

对于最小顶次数为n的任意单图,证明：存在一种（n-1)边着色,使与图中每顶关联的边中有（n-1)种颜色.（n>1)我又不是留学生，我们的书又不是英文版的，
对于最小顶次数为n的任意单图,证明：存在一种（n-1)边着色,使与图中每顶关联的边中有（n-1)种颜色.（n>1)
我又不是留学生，我们的书又不是英文版的，

对于最小顶次数为n的任意单图,证明：存在一种（n-1)边着色,使与图中每顶关联的边中有（n-1)种颜色.（n>1)我又不是留学生，我们的书又不是英文版的，
你这是定理吗?还是你自己的猜想呢?
补充：原题应该是英文的吧?把英文的发上来吧,更容易理解准确一些.
补充2：证明如下：（为了容易理解,我废话比较多.你慢慢看,不难.）
设图G的最小度数为n,我们要将边着色.
首先（不知你们学过没有）,我们要利用如下的一个很有名的定理：
如果图H的最大度数为n,那么H可(n+1)边着色,并且使得有公共顶点的边拥有不同的颜色.
为此,我们先构造图H.图H由图G演化而来,目的是要将G中顶点的度数统统变为n.为此,需要添加一些新的顶点.我们将会看到,新的顶点的度数统统为1.具体步骤如下：
（1）在G中任选一个度数大于n的顶点v,比如：v的度数是n+x.然后,构造x个新的顶点.再从与v相连的边中任选x条,将它们分别改为与这x个新的顶点相连.这一步过后,v的度数就变成了n,而新加的顶点度数都为1.
（2）重复步骤1.也就是说,看看当前图中还有没有度数大于n的顶点,如果有,则按照步骤1的方式去处理.直到没有了.
此时,我们观察一下这个新的图,也就是图H.先观察一下图H：
（1）图H中,原图G中的顶点的度数统统变为n,新加的顶点的度数全都是1.
（2）图H中的边与图G中的边一一对应,也就是说,给出任意一条图H中的边,我们都能把它还原成图G中的边.
下面,对图H应用那个定理.将图H进行(n+1)边着色,根据定理,每种颜色的边都不共点,也就是说,在每个顶点处,每种颜色的边只有1条或者0条.所以,对于原图G中的点,它们的度数为n,也就是说,它们与n条不同颜色的边相连,独缺1种颜色.
原题是要给出一个(n-1)边着色,下面,我们将保留前(n-1)种颜色,把最后2种颜色去掉.在图H中,我们把后2种颜色的边提取出来,记为E.看看由这些边组成的H的子图有什么性质.可以得出：在H中,每个顶点至多与2条E中的边相连.
对于H中一个原来G中的顶点,如果它不与E中的边相连,或者仅与1条E中的边相连,那么,即使去掉后2种颜色,它也已经有了(n-1)种不同的颜色.所以,关键是处理与E中2条边相连的那些顶点,把这些顶点记为U.
回想我们刚才的(n+1)边着色,每个G中的顶点都缺1种颜色.由于U中的顶点同时拥有了最后2种颜色,那么它们一定缺了前面的某一种颜色.当然,每个顶点缺的不一样.我们所要做的,就是将E中的边更改颜色,使得U中的每个点都有其中1条边改成了它缺的那种颜色.
再仔细看看H中由E中的边组成的子图,由于每个顶点至多与2条E中的边相连,所以这个子图的每一个连通分支,（1）或者是一条简单的路径；（2）或者是一个简单的回路.（上面这句话很显然,但需要想一下.）无论哪种情况,都可以给E中的边添加方向,使得每一个U中的点都有一个入边和一个出边.我们把每个U中点的入边改为该点所缺的颜色即可.
证明完了.

这道题？好像在哪里看过，我试试看。

设顶点数为m（m>n>=2）。
当m为偶数时，做如下处理：
（1) 由于一个单图中每个顶点的次数至少是2，就含有一个圈，将圈中没有公共顶点的边删除一遍，并将这些边染同一种颜色i（第i次 操作染第i种颜色）。那么每个点 都有颜色i的边，且最小顶次数变为（n-1）。
（2)重复上述步骤至最小顶次数为1，即一共进行了（n-1）次操作（1），每点都有（n-1）种颜色的...

全部展开

设顶点数为m（m>n>=2）。
当m为偶数时，做如下处理：
（1) 由于一个单图中每个顶点的次数至少是2，就含有一个圈，将圈中没有公共顶点的边删除一遍，并将这些边染同一种颜色i（第i次 操作染第i种颜色）。那么每个点 都有颜色i的边，且最小顶次数变为（n-1）。
（2)重复上述步骤至最小顶次数为1，即一共进行了（n-1）次操作（1），每点都有（n-1）种颜色的边，即符合命题。
当m为奇数时，作如下处理：
同做（1）处理，但是处理后剩余1个点没有被删除的边包含。该点记为Vi。
同做（2）处理，注意每次剩余不同的点。此时最小顶次数为1，除Vi（i=1，2，3..n-1）值有（n-2）种颜色外，每点都有（n-1）种颜色的边。
此时Vi（i=1，2，3..n-1）度大于等于2，此时再做如下处理：
取一条包含V1的边染成V1缺少的颜色并删除，然后取包含Vi（i=1，2，3，4...n-1）中除去已经取过的度数最小的点的边染成该边缺少的颜色，重复操作至每个Vi（i=1，2...n-1）都添加缺少颜色的边即可。此时每顶都有（n-1）种颜色的边，符合命题。

收起

著名难题！