设G是2n阶无向简单图,且G的每个顶点至少与另外n个顶点相邻,证明G是连通图
时间: 2024-03-29 10:36:17 浏览: 18
首先,我们可以使用反证法来证明这个命题。假设G不是连通图,那么G可以被分为两个或更多个不相交的连通分量。假设这两个连通分量的大小分别为a和b,则n ≤ a, b ≤ 2n − n = n。因为每个顶点至少与另外n个顶点相邻,所以G中至少有a × n 条边和b × n 条边。因此,G中总共至少有an + bn 条边。
然而,G是2n阶无向简单图,所以它最多有n × (2n − 1) 条边。由于an + bn ≥ n × 2n,所以an + bn > n × (2n − 1)。这与G最多有n × (2n − 1) 条边矛盾。因此,假设不成立,即G是连通图。
因此,我们证明了G是连通图。
相关问题
设G是边数m小于30的简单平面图,试证明:G中存在顶点可,deg(v)≤4。
我们可以使用反证法来证明:假设G中所有顶点的度数都大于4,那么G中的所有顶点的度数之和2m一定大于4n,其中n为G中的顶点数。
根据欧拉公式,对于一个边数小于30的简单平面图,有n-m+f=2,其中f为G的面数,因为G是一个简单平面图,所以每个面至少有3条边,所以2m≥3f。将这个式子代入上面的不等式中得到:
4n<2m≤3f,即2n<f。又因为每个面至少有3条边,所以f≤2m/3,代入上式得到2n<2m/3,即3n<2m,与欧拉公式n-m+f=2不符。
所以假设不成立,必然存在一个顶点v,使得deg(v)≤4。证毕。
n阶无向树的所有顶点度数之和是( (2分) a:2(n+1) o b: 2n
题目中涉及到的n阶无向树是指有n个顶点的树,其中顶点度数是指与该顶点相连的边的数量。
对于无向树中的每个顶点,它的度数可以是0、1、2、...、n-1或n。由于无向树中的边数与顶点数n相关,所以边的总数为n-1。每个边连接两个顶点,因此无向树的所有顶点度数之和应该是边的总数的两倍。
所以答案是b: 2n。