无向连通图所有顶点的度数之和为偶数

证：

设无向连通图 $G=(V,E)$ 中有 $n$ 个顶点，$m$ 条边。则 $G$ 的所有顶点的度数之和为：

$$
\sum_{v\in V} \deg(v) = 2m
$$

其中 $\deg(v)$ 表示顶点 $v$ 的度数。

我们知道，每条边都会贡献 $2$ 到度数之和中，因为每条边连接了 $2$ 个顶点，每个顶点的度数都会加 $1$。因此，上式中的 $2m$ 就是所有顶点度数之和的总和。

而一个数能够被 $2$ 整除，当且仅当它的最低位为 $0$。因此，如果所有顶点的度数之和为偶数，那么它的二进制表示的最低位为 $0$，也就是说，每个顶点的度数都是偶数。

因为 $G$ 是一个无向图，所以每个顶点的度数就是它所连接的边数。如果所有顶点的度数都是偶数，那么每条边的两个端点的度数均为偶数。因此，每条边贡献 $2$ 到所有顶点度数之和中，也就是说，所有顶点度数之和为偶数。

综上所述，无向连通图所有顶点的度数之和为偶数。

相关问题

欧拉图判断: 先判断图是否连通，非连通图则是非欧拉图。 对无向连通图而言，若所有结点的度都是偶数，则该图为欧拉图。 对无向连通图而言，若只有两个结点的度数是奇数，其余结点度数为偶数，则该图为半欧拉图。 判断一个图是否欧拉图 若是欧拉图，则输出"a is euler”； 若是半欧拉图，则输出"a is semi-euler”； 若不是欧拉图，则输出“a is not euler”。 注意：该输出前后无空格，行尾回车。 输入格式: 第一行输入结点数n（n<=10），第二行输入无向图关系矩阵的上三角元素为1的一对结点编号，结点编号之间以空格分隔；第三行输入无向图关系矩阵的下三角元素为1的一对结点编号，结点之间以空格分隔。输入 -1 -1则结束输入。 输出格式: 输出a是否欧拉图、半欧拉图或者不是欧拉图。 输入样例: 在这里给出一组输入(上图的关系矩阵)。例如： 9 0 1 1 2 0 3 1 3 1 4 3 4 2 5 4 5 3 6 4 7 5 7 5 8 6 7 7 8 1 0 2 1 3 0 3 1 4 1 4 3 5 2 5 4 6 3 7 4 7 5 8 5 7 6 8 7 -1 -1 输出样例: 在这里给出相应的输出。例如： a is euler

以下是使用C++实现的代码：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 15;
int g[N][N];
int n;
int deg[N];

int bfs(int u)
{
    queue<int> q;
    q.push(u);
    bool st[N];
    memset(st, 0, sizeof st);
    st[u] = true;

    int cnt = 0;

    while (q.size())
    {
        auto t = q.front();
        q.pop();
        cnt ++;

        for (int i = 0; i < n; i ++ )
            if (g[t][i] && !st[i])
            {
                st[i] = true;
                q.push(i);
            }
    }

    return cnt;
}

int main()
{
    memset(deg, 0, sizeof deg);

    int a, b;
    cin >> n;
    while (cin >> a >> b, a != -1 && b != -1)
        g[a][b] = g[b][a] = 1, deg[a] ++ , deg[b] ++;

    int cnt = bfs(0);
    bool flag = true;
    for (int i = 0; i < n; i ++ )
        if (!deg[i])
        {
            flag = false;
            break;
        }

    if (!flag || cnt < n) puts("a is not euler");
    else if (cnt == n) puts("a is euler");
    else
    {
        int odd = 0;
        for (int i = 0; i < n; i ++ )
            if (deg[i] & 1)
                odd ++;

        if (odd == 2) puts("a is semi-euler");
        else puts("a is not euler");
    }

    return 0;
}

该程序首先读入图的顶点数n和图的边。然后使用邻接矩阵表示图，并计算每个顶点的度数。接下来，使用BFS遍历图，并记录遍历到的节点数cnt。然后，遍历每个顶点的度数，如果有顶点的度数为0，则该图不是连通图，输出“a is not euler”。如果遍历到的节点数cnt小于n，则该图不是连通图，输出“a is not euler”。否则，如果每个顶点的度数都是偶数，则输出“a is euler”。如果只有两个顶点的度数是奇数，则输出“a is semi-euler”，否则输出“a is not euler”。

输入一个无向连通图的，判断这个图是否存在欧拉回路，如果没有则输出“no oula circle”，如果有，输出以顶点1开始的一条欧拉回路，回路上顶点序号优先小的。 输入描述 第一行一个整数 n 和 k，表示这个图有 n 个顶点、k 条边，接下来 k 行，每行两个整数 a i ​ 和 a j ​ ，表示顶点 a i ​ 和 a j ​ 之间有一条边。 输出描述 如果不存在欧拉回路，请输出“no oula circle”，如果有欧拉回路，请输出顶点 1 开始的欧拉回路的顶点编号。

好的，这是一个图论问题，可以使用深度优先搜索或广度优先搜索来解决。首先需要判断这个图是否连通，如果不连通，则不存在欧拉回路。如果连通，则需要判断每个顶点的度数是否为偶数，如果有一个顶点的度数为奇数，则不存在欧拉回路。否则，从任意一个顶点开始进行深度或广度优先搜索，每次遍历到一个边就将其删除，直到无法继续遍历为止。如果所有边都被遍历到了，则存在欧拉回路，否则不存在。

下面是实现代码：