一个连通无向图有3个5度点、1个4度点、3个2度点,其它都是1度,那么它的顶点个数≤?
时间: 2024-02-16 09:01:26 浏览: 91
设该图有 $n$ 个顶点,则它的边数为 $E=\frac{1}{2}\sum_{i=1}^{n} d_i$,其中 $d_i$ 表示第 $i$ 个顶点的度数。根据握手定理,边数和度数之和相等,即 $\sum_{i=1}^{n} d_i=2E$。
将题目给出的度数代入上式,得到:$$\begin{aligned} \sum_{i=1}^{n} d_i &= 3\times5+1\times4+3\times2+(n-7)\times1 \\ &= 15+4+6+(n-7) \\ &= n+18 \end{aligned}$$
又因为该图是连通的无向图,所以根据欧拉公式有 $E=n-1$。代入上式,得到:$$\begin{aligned} n+18 &= 2E \\ &= 2(n-1) \\ &= 2n-2 \end{aligned}$$
解得 $n=20$。因此,该图的顶点个数不超过 20 个。
阅读全文