给定一个图G= (V，E)，证明e <= n(n-1)/2
给定一个图G= (V，E)，证明e <= n(n-1)/2
提问于 2016-01-12 10:09:16
我正在尝试解决这个问题:给定一个图G= (V，E) prove e <= n( n -1)/2，其中e是边的数量，n是顶点的数量。
我在想，我应该以某种方式使用数学归纳法来找出正确的答案，并使用n=1或0作为我的假设，但我对之后要做的事情有点纠结--如果我假设n= k，那么:e <= ( k+1 )k/2。如果n=k+1，那么e <= k(k-1)/2。
据我所知，每个顶点有n-1条可能的边出来，总共有n个顶点，这就是n(n-1)的来源，除以2可以去掉重复。但我不确定我该如何证明这一点。
回答 1
Stack Overflow用户
发布于 2016-01-14 19:45:09
对于多图，该语句是错误的。以图为例：
/---\
O-----O有两个顶点(O)和两条边；因此，n=2,e=2和代入n(n-1)/2 <= e会得到1 <= 2，这是假的。
但是，如果您将图限制为简单-不允许循环边(边的两端终止于同一顶点)、多边(两条边连接同一对顶点)以及图是无向的-则该属性成立。
考虑一个完整的图K_n (具有n顶点)：每个n顶点通过连接边与其他n-1顶点关联，因此从一个顶点到另一个顶点有n(n-1)连接；如果边是无向的，那么这将计算每条边两次(即从顶点A到顶点B，反之亦然)，那么边的总数将是n(n-1)/2。
任何图G_n (具有n顶点)都将是K_n的子图(由于在不创建多重边或循环边的情况下无法向K_n添加更多边)，则G_n中的边必须等于或少于K_n中的边。
因此，对于所有简单的图，都是e <= n(n-1)/2。
如果进一步将图形限制为平面，则可以声明该e <= 3n - 6 (当为n > 2时)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/34734464
复制相关文章
相似问题
腾讯云开发者
