证明:若G=〈V,E〉是简单图,则m≤Cn2 ,其中m为图的边数,n为图的顶点数.
问题描述：
证明:若G=〈V,E〉是简单图,则m≤Cn2 ,其中m为图的边数,n为图的顶点数.
我不太懂题目的意思,
答
假设G中每个顶点的度数最大=2
边数=2n/2=n很感谢你，能不能告诉我为什么假设G中每个顶点的度数最大=2，然后得出G中至少有一个顶点的度数大于或等于3这个结论，这和题目有什么必然关系吗不好意思啊，离散数学忘记了不少，其实那个假设是做题的习惯，反证法。我是这样想的，假设所有顶点的度数最多为2，则度数总和D ≤ 2n ≠ 2(n+1)，与握手定理矛盾。