结构推理
设无向图G=(V，E)中，|E|=12，若G中有6个3次结点，其余结点次数均小于3，则G中至少要有多少个结点?根据是什么?
【正确答案】
9，∑
i=1
n
deg(v
i
)=2|E|
【答案解析】
因为总度数等于边数的2倍，即2×12=24．已知图中已有6个3度结点，其度数和为6×3=18，24-18=6，而其余结点度数均小于3，即最大度数为2，而6至少要分担到3个度数为2的结点上，故G中至少要有6+3个结点，即9个．
提交答案
关闭