G是n阶简单无向图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图_数学解答

G是n阶简单无向图,如果图G中任意两点的度数之和大于等于n-1,证明图G是连通图

人气：124 ℃　时间：2020-04-09 08:46:42

解答

假设G有两个连通分支G1和G2,那么取v1是G1中度数最小的顶点,v2是G2中度数最小的顶点,则d(v1)+d(v2)≤n-2（等号在G1和G2都是完全图时取到）,这与条件矛盾.