简单图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个顶点时,图中所能容纳的边数达到最大。此时边数e_max=(n-1)(n-2)/2,与已知矛盾。故G必是连通图。证毕

↑

简单图G有n个顶点,e条边,若e> (n-1)(n-2)/2,证明G是连通图。

相关题目