G 是简单图，已知 E(G)＞C(V(G)-1,2)，证明 G 是连通图

wilsony · 发表于 2025-8-1 09:39

谁能证明？

wilsony · 发表于 2025-8-1 20:43

这道题关系到一个组合不等式，不知谁能证明？

luyuanhong · 发表于 2025-8-2 10:18

luyuanhong · 发表于 2025-8-2 10:19

luyuanhong · 发表于 2025-8-2 10:20

题 G 是简单图，E(G) 是图中的边数，V(G) 是图中的顶点数，证明：E(G)≤C(V(G),2) 。

证  图 G 中共有 V(G) 个顶点，如果在图中任何两个顶点之间，都连一条边，则总共可连

            V(G)×[V(G)-1]／2 = C(V(G),2) 条边。

因为 G 是简单图，两点之间最多连一条边，不可能再有其他的边了，所以图中的边数

               E(G)≤C(V(G),2) 。

wilsony · 发表于 2025-8-2 15:30

多谢陆老师指教！

luyuanhong · 发表于 2025-8-2 18:20

wilsony · 发表于 2025-8-3 08:02

多谢陆老师！

		自动登录	找回密码
密码			注册

G 是简单图，已知 E(G)＞C(V(G)-1,2)，证明 G 是连通图

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源

本帖子中包含更多资源