问给出n点无向连通图的最小边数和最大边数？

EN

是的..无向连通图的最小边数是(n-1)边。要看到这一点，由于图是连接的，那么从每个顶点到每个其他顶点必须有一条唯一的路径，删除任何边都会使图断开连接。

对于最大边数(假设简单图)，每个顶点都连接到所有其他顶点，这给出了n(n-1)/2边的出现(使用握手引理)。另一种方法:查看具有最大边数的K_n (具有n个顶点的完整图)。

声明:如果有N个顶点，则最小值为N-1，最大值为N*(N-1)/2

证明：

考虑一个邻接矩阵，其中元素可以是1(表示存在边)，也可以是0(表示没有边)。对于要连接的图，在上三角形的每一行中必须至少有一个"1“。

最小是通过在上三角形的每一行中仅放置1来实现的。现在，如果邻接矩阵是N乘N，则第一行在上三角形中有N-1个元素，第二行在上三角形中有N-2个元素，...，最后一行在上三角形中有0个元素。也就是说，总共有N-1行“有一个上三角形”，每行只有一个1。因此，N-1中的边数。

如果上三角形的每个元素都有1，则会出现最大。现在，整个矩阵的上三角形中的元素数为

1+2+ ... + (N-2) + (N-1) = N*(N-1)/2。

关于最后一个等式，请回忆一下微积分课程的有限和。请参见此处的第二个公式，并将"m“替换为(N-1)"：https://en.wikipedia.org/wiki/List_of_mathematical_series#Sums_of_powers

PS:我真的希望我可以在SO上使用LaTeX！