简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。
简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。
【正确答案】：证明:G= ,l Ⅴ l=n,若G不是连通图,则W(G)≥2。
 非连通图仅当连通分量为2,且顶点集分别含n-1个顶点及1个顶点时,图中所能容纳的边数达到最大。此时边数emax=(n-1)(n-2)/2,与已知矛盾。故G必是连通图。   证毕
Top
×
×