> 数学 >
求教离散数学:证明任意一个具有6个顶点的简单图或其补图一定包含一个三角形.
人气:468 ℃ 时间:2020-02-15 08:49:47
解答

证明:

1)设6个顶点的图为G1,其补图为G2,则完全图G= G1∪G2.

2)对于完全图G,v1与其他5个顶点相连,设图G1用红色线表示,G2用蓝色线表示,对于V1与其他顶点相连的5条线中,用两种颜色表示的情况下,必有一种颜色的线大于等于3,如图所示,假设红色线数大于等于3.


3)图示中三条边(V2,V3),(V3,V4),(V2,V4),任意一条边为红色,则必存在一个三角形,如果这三条边都不为红色,则为蓝色,必有这三条蓝色边形成一个三角形.

推荐
猜你喜欢
© 2024 79432.Com All Rights Reserved.
电脑版|手机版