为什么度数之和等于结点数减一呀

Question

为什么度数之和等于结点数减一呀？
这又不是树，很不理解是那个定理给看差了

Answer 1

引自免费微信小程序：皆我百晓生

在图论中，一个无向图的每个边连接两个节点。当我们计算所有节点的度数总和时，每条边会对两个节点的度数各贡献1。例如，如果一个边连接节点A和节点B，那么这条边会使A的度数增加1，同时也会使B的度数增加1。因此，每条边实际上被算了两次。

考虑一个无向简单图G，它有n个节点和m条边。如果我们把所有节点的度数加起来，我们将会得到所有边的两倍数量。这是因为每条边对两个节点的度数都有贡献。所以我们可以写出公式：

[ \sum_{v \in V(G)} deg(v) = 2m ]

其中( V(G) )代表图G的所有节点集合，( deg(v) )代表节点v的度数。

然而，图G的补图G'中的边与原图G中的边是互补的。也就是说，如果在G中有两条不相邻的节点u和v，那么在G'中有一条边连接它们；反之亦然。因此，对于一个n阶的无向简单图，其补图也有同样的节点数n。由于原图G有m条边，其补图G'就有( n(n-1)/2 - m )条边（因为总的可能边数为( n(n-1)/2 )，已知边数为m）。同样地，补图的节点度数之和也是边数的两倍：

[ \sum_{v \in V(G')} deg'(v) = 2\left(\frac{n(n-1)}{2} - m\right) ]

接下来我们要证明的是奇度节点的数目在原图G和补图G'中相同。首先，我们注意到总边数m加上补图的边数( n(n-1)/2 - m )等于总可能的边数( n(n-1)/2 )。这是因为原图和补图一起包含了所有可能的边：

[ m + \left(\frac{n(n-1)}{2} - m\right) = \frac{n(n-1)}{2} ]

简化这个方程得：

[ \frac{n(n-1)}{2} = m ]

现在回到度数之和的公式：

[ \sum_{v \in V(G)} deg(v) = 2m ] [ \sum_{v \in V(G')} deg'(v) = 2\left(\frac{n(n-1)}{2} - m\right) ]

将( m = n(n-1)/4 )代入上述两个公式，我们得到：

[ \sum_{v \in V(G)} deg(v) = n(n-1) ] [ \sum_{v \in V(G')} deg'(v) = n(n-1) ]

这样我们就知道原图G和补图G'的节点度数之和都是( n(n-1) )。这恰好等于结点数n乘以(n-1)，而不是结点数减一。因此，这里并没有说度数之和等于结点数减一，而是度数之和等于结点数乘以(n-1)。

至于题目要求证明奇度节点的个数相等，我们可以通过以下方式来理解：

设在一个无向简单图中，某个节点v的度数为偶数，则它的补图中对应的节点v的度数也必定是偶数，因为它们共享相同的邻居。同理，如果原图中某节点v的度数为奇数，那么在补图中它的度数将是奇数，因为它们在补图中会形成一对新的邻接关系。因此，原图中奇数度节点的数量等于补图中奇数度节点的数量。这与度数之和无关，只是关于奇偶性的一个性质。