【正确答案】：证明:G=
若G不是连通图,即W(G)≥2。对任一个连通分量,因每个顶点度数至少为n,且G为简单图,没有多重边及自悬边,故连通分量中所含顶点的个数≥n+1,
l Ⅴ l≥2(n+1)=2n+2,与l Ⅴ l≤2n矛盾。所以G必为连通图。 证毕
若简单图至多有2n个顶点,每个顶点度数至少为n,G必为连通图。
- 2024-08-04 00:07:45
- 离散数学(02324)
- 1
若简单图至多有2n个顶点,每个顶点度数至少为n,G必为连通图。
【正确答案】：证明:G= ,l Ⅴ l≤2n,deg(vi)≥n。
若G不是连通图,即W(G)≥2。对任一个连通分量,因每个顶点度数至少为n,且G为简单图,没有多重边及自悬边,故连通分量中所含顶点的个数≥n+1,
l Ⅴ l≥2(n+1)=2n+2,与l Ⅴ l≤2n矛盾。所以G必为连通图。 证毕
【正确答案】：证明:G=
若G不是连通图,即W(G)≥2。对任一个连通分量,因每个顶点度数至少为n,且G为简单图,没有多重边及自悬边,故连通分量中所含顶点的个数≥n+1,
l Ⅴ l≥2(n+1)=2n+2,与l Ⅴ l≤2n矛盾。所以G必为连通图。 证毕