设图G=(V,E)有n个顶点,2n条边,且存在一个度数为3的顶点,证明：G中至少有一个顶点的度数≥5_数学解答

设图G=(V,E)有n个顶点,2n条边,且存在一个度数为3的顶点,证明：G中至少有一个顶点的度数≥5

人气：466 ℃　时间：2020-05-30 13:03:31

解答

m为边数,则 Σd(v) = 2m = 4n
反证：若任一点v有d(v)≤4且存在一点v0有d(v0)=3
则Σd(v)≤4n-1,矛盾大神，再帮忙看看其他题目呗