Question

证明:若G=〈V,E〉是简单图,则m≤Cn2 ,其中m为图的边数,n为图的顶点数.

我不太懂题目的意思，也不会做，求教各位

Answer 1

假设G中每个顶点的度数最大=2
边数=2n/2=n<n+1
与题设矛盾
所以G中至少有一个顶点的度数大于或等于3

边数=2n/2=n<n+1，以条边2个顶点，用度数×顶点数/2=变数，好像书上有这公式的

追问

很感谢你，能不能告诉我为什么假设G中每个顶点的度数最大=2，然后得出G中至少有一个顶点的度数大于或等于3这个结论，这和题目有什么必然关系吗

追答

不好意思啊，离散数学忘记了不少，其实那个假设是做题的习惯，反证法。
我是这样想的，假设所有顶点的度数最多为2，则
度数总和D ≤ 2n ≠ 2(n+1)，与握手定理矛盾。