证明至少有五个顶点的简单图包含一个圈

Question

若G是至少有五个顶点的简单图，证明：G或者G的补图包含一个圈。

Answer 1

n阶完全图的边数为C(n,2)=n(n-1)/2,
根据抽屉原理
G和G补中至少有一个含有至少[n(n-1)/4]条边
n>=5时[n(n-1)/4]>n-1
即边数比n阶的树要大,则这个图是非树简单图,所以含有圈.