图对于图G= ,其中 |V| =n,|E|=n+1 ,证明G中至少有一个结点的度数≥3
问题描述：
图
对于图G= ,其中 |V| =n,|E|=n+1 ,证明G中至少有一个结点的度数≥3
答
二楼正解
答
还没学离散
答
证明 反证法,如果G中所有结点的度数均小于3,或不超过2,则n个结点度数之和不超过2n,结点度数之和等于边数的2倍,即结点度数之和=2|E|=2n+2,故有2n≥2n+2,n≥n+1,矛盾.