作业帮 > 数学 > 作业

证明:如果G是一个(p,q)图,q>1/2(p-1)(p-2),试证明G是连通图

来源:学生作业帮 编辑:作业帮 分类:数学作业 时间:2024/07/09 08:41:27
证明:如果G是一个(p,q)图,q>1/2(p-1)(p-2),试证明G是连通图
G是一个简单图.
用反正法,假设命题不成立,则p个点中至少有一个点是孤立点,不妨设第p个点是孤立点,则G1=(p-1,q)也是简单图,这与p-1个点的简单图(简单图任意两点最多有一条边)的边数不超过1/2(p-1)(p-2)条边矛盾,因此假设不成立,原命题得证