对于最小顶次数为n的任意单图,证明：存在一种（n-1)边着色,使与图中每顶关联的边中有（n-1)种颜色.（n>1)

来源：学生作业帮编辑：百度作业网作业帮分类：数学作业时间：2024/04/29 01:38:46

对于最小顶次数为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中点的入边改为该点所缺的颜色即可.
证明完了.

对于任意正整数n，猜想2n-1与（n+1）2的大小关系，并给出证明．高中不等式证明问题对于任意的n∈N*,试比较n!与2^(n-1)的大小,证明你的结论 n为正整数,证明在任意(n+1)个正整数中,至少存在两个数,它们的差为n的倍数为什么对于任意奇数n都存在x使2^x mod n = 1 希望能给出好的数学证明,或者给出具体的定理名对于任意整数n按下列程序计算n----立方------2n------÷n----+1的答案为? 对于任意正整数n,整式（3n+1)(3n-1)-(3-n)(3+n)的值是否是十的倍数,请证明出来证明对于大于1的任意正整数n都有 In n>1/2+1/3+1/4+...1/n 证明:对任意的n属于N不等式eln（(n+1）/n) 设n为任意整数,试证明n(n+1)(2n+1)是6的倍数不等式数学证明题证明：对于任意的正整数n,不等式ln(1/n+1)>1/n^2-1/n^3都成立证明对任意n,任意2n-1元正整数集合,一定存在n个元素,使得他们的和是n的倍数证明：n>=1,n为整数.证（（n-1）*n）/2 的奇偶性与 n+1 相同.