如何证明最大度是k的无向图的边色数是2k-1？

设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k（k>=2），证明T中至少有2k-2片树叶~

T中有三种点总共n个，设这三种点的个数：
k度点 2 个
1度叶结点 e叶 个
其余点 v' 个，他们度数为[2,k-1)范围内
可列以下公式：
e叶+2+v'=n
e叶+2k+pv'=2n-2（总度数为2n-2）
2≤p<k
解上述方程组，得e叶≥2k-2。

先假设G不是连通的，则G至少有两个连通分支G1和G2,有 |G1|+|G2| ≤ |G| = n；
任取G1中一点v1,G2中一点v2，则d(v1)≤|G1|-1,d(v2)≤|G2|-1；
d(v1)+d(v2) ≤ |G1|+|G2|-2 ≤ n-2，与条件矛盾，故G只能是连通图。
在图论中，连通图基于连通的概念。在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。如果 G 是有向图，那么连接i和j的路径中所有的边都必须同向。如果图中任意两点都是连通的，那么图被称作连通图。
如果此图是有向图，则称为强连通图。而无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。
扩展资料：
连通图性质
一个无向图 G=(V,E) 是连通的，那么边的数目大于等于顶点的数目减一：|E|>=|V|-1，而反之不成立。
如果 G=(V,E) 是有向图，那么它是强连通图的必要条件是边的数目大于等于顶点的数目：|E|>=|V|，而反之不成立。
没有回路的无向图是连通的当且仅当它是树，即等价于：|E|=|V|-1。
参考资料：百度百科-连通图

运用运筹学里的统计归纳法证明。

可以用归纳法来证明。

归纳推理是一种由个别到一般的推理。由一定程度的关于个别事物的观点过渡到范围较大的观点，由特殊具体的事例推导出一般原理、原则的解释方法。自然界和社会中的一般，都存在于个别、特殊之中，并通过个别而存在。一般都存在于具体的对象和现象之中，因此，只有通过认识个别，才能认识一般。人们在解释一个较大事物时，从个别、特殊的事物总结、概括出各种各样的带有一般性的原理或原则，然后才可能从这些原理、原则出发，再得出关于个别事物的结论。这种认识秩序贯穿于人们的解释活动中，不断从个别上升到一般，即从对个别事物的认识上升到对事物的一般规律性的认识。例如，根据各个地区、各个历史时期生产力不发展所导致的社会生活面貌落后，可以得出结论说，生产力发展是社会进步的动力，这正是从对于个别事物的研究得出一般性结论的推理过程，即归纳推理。显然，归纳推理是从认识研究个别事物到总结、概括一般性规律的推断过程。在进行归纳和概括的时候，解释者不单纯运用归纳推理，同时也运用演绎法。在人们的解释思维中，归纳和演绎是互相联系、互相补充、不可分割的。

例如：在一个平面内，直角三角形内角和是180度；锐角三角形内角和是180度；钝角三角形内角和是180度；直角三角形，锐角三角形和钝角三角形是全部的三角形；所以，平面内的一切三角形内角和都是180度。

这个例子从直角三角形，锐角三角形和钝角三角形内角和分别都是180度这些个别性知识，推出了“一切三角形内角和都是180度“这样的一般性结论，就属于归纳推理。

传统上，根据前提所考察对象范围的不同，把归纳推理分为完全归纳推理和不完全归纳推理。完全归纳推理考察了某类事物的全部对象，不完全归纳推理则仅仅考察了某类事物的部分对象。并进一步根据前提是否揭示对象与其属性间的因果联系，把不完全归纳推理分为简单枚举归纳推理和科学归纳推理。

现代归纳逻辑则主要研究概率推理和统计推理。归纳推理的前提是其结论的必要条件。

其次，归纳推理的前提是真实的，但结论却未必真实，而可能为假。如根据某天有一只兔子撞到树上死了，推出每天都会有兔子撞到树上死掉，这一结论很可能为假，除非一些很特殊的情况发生，比如地理环境中发生了什么异常使得兔子必以撞树为快。

我们可以用归纳强度来说明归纳推理中前提对结论的支持度。支持度小于50%的，则称该推理是归纳弱的；支持度小于100%但大于50%的，称该推理是归纳强的；归纳推理中只有完全归纳推理前提对结论的支持度达到100%，支持度达到100%的是必然性支持。

归纳推理的数理逻辑通用演算形式为：s1⊆p+s2⊆p+s3⊆p+〈n〉（s⊆p）=∀×（s⊆p）。

希望我能帮助你解疑释惑。

---

温宿县13176318153： 设一个无向图G=(V,E)有n个顶点n+1条边,证明G中至少有一个顶点的度数大于或等于3. - ？
谷促荷洛： 假设G中每个顶点的度数最大等于2 边数=2n/2=n<n+1 与题设矛盾 所以G中至少有一个顶点的度数大于或等于3 边数=2n/2=n<n+1 前面的2是度数.以条边2个顶点,用度数*顶点数/2=变数,好像书上有这公式的

温宿县13176318153： 设一个无向图有5顶点,度数分别是4,3,3,2,2,求该图边数 - ？
谷促荷洛： 7条边.数据结构的书上应该有证明.每条边与两个顶点相连接,所以所有顶点上的度数之和就是图中边的两倍,本题中共有4+3+3+2+2=14个边的端点,因而共有14/2=7条边

温宿县13176318153： 若一个具有N个顶点,K条边的无向图是一个森林N>K则森林有几棵树 - ？
谷促荷洛： N-K 很简单,具有M个顶点的树恰有M-1条边.

温宿县13176318153： 离散数学中 已知n阶m条边的无向图G为k(k>=2)个连通分支的森林,证明m=n - k - ？
谷促荷洛： 连通分支之间添加一条边,总共添加k-1条边,G就是树了,边数是n-1,所以m+k-1=n-1,得m=n-k

温宿县13176318153： 如何证明小于30条边的平面简单图有一个结点的度数小于等于4 - ？
谷促荷洛： 设无向图中顶点个数为 N, 则边数最大为 N*(N-1)/2 假设所有结点的度数都大于4, 则总度数>4N 边数=总度数/2 > 2N N*(N-1)/2 > 2N N>5 边数> 6*(6-1) =30条 与题目所给矛盾, 所以小于30条边的平面简单图有一个结点的度数小于等于4

温宿县13176318153： 若一个具有n个顶点,k条边的无向图是一个森林,则森林中必有多少棵树 - ？
谷促荷洛： 如果某棵树中有N0个结点,K0条边,则N0 = k0 + 1 设森林中有m棵树,其结点数分别为n1,n2,n3,.,nm 相应地,各棵树的边数分别为k1,k2,k3,...km 显然:n1 = k1 + 1,n2 = k2 + 1,.,nm = km + 1 (1) 按照题设: n1 + n2 + n3 +.+ nm = N (2) k1 + k2 + ...

温宿县13176318153： 设无向连通图G有n个顶点,证明G至少有(n - 1)条边. - ？
谷促荷洛： 设连通图G有(n+1)个顶点,若每个顶点连出至少两条边,那么此时至少有n+1条边(任意图上所有顶点度数和等于边数的两倍),结论已经成立.否则,那么至少有一个顶点只连出一条边. 不妨设为A,由于去掉这条边AB后不影响其他点的...

温宿县13176318153： 用△记G中顶点的最大度.证明:若G是△≥k的树,则G中至少有k个顶点的度为1. - ？
谷促荷洛：[答案] 考虑具有最大度数的顶点所在的连通子树,设其有n个顶点,可知其有n-1条边,顶点度数和2(n-1). 因其连通,每个顶点的度数≥1.设有m个顶点度数为1,则其余顶点度数≥2,且有一个度数≥k. 总度数2(n-1)≥m+2(n-m-1)+k,即有m≥k.

温宿县13176318153： “在顶点个数不少于2的简单无向图中,必有度数相同的顶点”的证明过程? - ？
谷促荷洛： 对点数n归纳 n=2成立 设n=k成立n=k+1时 1)若有一点度数为0,去掉这点,则剩下k个点必有2个度数相同的顶点 2)若每点度数至少为1,而所有点对数都至多为k,k+1个点,度数都是1至k的整数,由抽屉原理得必定至少有2个度数相同的顶点 归纳法对n=k+1也成立所以在顶点个数不少于2的简单无向图中,必有度数相同的顶点

温宿县13176318153： 判断无向图中是否有环 - ？
谷促荷洛： 如果存在回路,则必存在一个子图,是一个环路.环路中所有顶点的度>=2. n算法: 第一步:删除所有度<=1的顶点及相关的边,并将另外与这些边相关的其它顶点的度减一. 第二步:将度数变为1的顶点排入队列,并从该队列中取出一个顶...