s******r
发帖数: 9 | 1 建立图G(V,E)如下:
V={v1,v2,...,v9}.
E={(v1,v2) | 如果v1,v2握过手}
这样,|E|=(1*2+2*4+4*5+2*6)/2=21
利用定理:如果图G(V,E)不存在三角形,则 |E|<=n*n/4 (n为点数)
因为 21>9*9/4, 所以存在三角形 (v_i,v_j,v_k).
于是,v_i,v_j,v_k 三人互相握过手.
定理的证明(Hint): Observe that for each edge (x,y), there
exist a
inequality:
deg(x)+deg(y)<=n,
add all these inequalities together. |
|
