无向图G有23条边,度为4的顶点有5个,度为3的顶点有4个,其余都是度为2的顶点,则图G最多有( )个顶点。
A、
11
B、
12
C、
15
D、
16
【正确答案】
D
【答案解析】
解析:顶点的度是指与此顶点相关联的边数,而每条边与两个顶点相关联。23条边最多有46个顶点(不排除多条边共享一个顶点),设图G中有n个顶点,则有4×5+3×4+(n-5-4)×2≤23×2,解得n≤16。
提交答案
关闭