图对于图G= ,其中 |V| =n,|E|=n+1 ,证明G中至少有一个结点的度数≥3_数学解答

图
对于图G= ,其中 |V| =n,|E|=n+1 ,证明G中至少有一个结点的度数≥3

人气：397 ℃　时间：2020-05-11 14:42:54

解答

证明反证法,如果G中所有结点的度数均小于3,或不超过2,则n个结点度数之和不超过2n,结点度数之和等于边数的2倍,即结点度数之和=2|E|=2n+2,故有2n≥2n+2,n≥n+1,矛盾.