Question

离散数学，图，求助。

3.设G=(VE)是简单无向连通图,但不是完全图,求证: G中必然存在3个结点u,v,w∈V，uv,vw∈E,但uw∉E.

Answer 1

证明
因为G不是完全图，所以存在两个顶点u,w∈V,uw∉E.因为G是无相连通图，所以存在一条连接u,w的路：
u,u(1),u(2),...,u(n),w。
假设不存在3个结点u,v,w∈V，uv,vw∈E,但uwE.因此，如果u,v,w∈V，uv,vw∈E,必有uw∈E.
考虑u,u(1),u(2)，因为u,u(1),u(2)∈V，uu(1),u(1)u(2)∈E,所以uu(2)∈E
去掉u(1),得到一条新的连接u,w的路
u,u(2),u(2),...,u(n),w。
不断重复上述过程，最后得到连接u,w的路
u,u(n),w。
根据假设，uw∈E,这与uw∉E矛盾。
所以结论成立。