一个含4个结点的无向图中有3个结点的度数分别为1，2，3，则第4个结点的度数不可能是

第4个结点的度数不可能是2。因为如果第4个结点的度数为2，则这个图可以看作是由一条边和两个有度数3的结点组成的，这样就无法满足第1个结点的度数为1的条件。同样地，第4个结点的度数也不可能是3，因为如果第4个结点的度数为3，则这个图可以看作是由一个三角形和一个度数为1的结点组成的，这样就无法满足第2个结点的度数为2的条件。因此，第4个结点的度数只能是0或4。

相关问题

欧拉图判断: 先判断图是否连通，非连通图则是非欧拉图。 对无向连通图而言，若所有结点的度都是偶数，则该图为欧拉图。 对无向连通图而言，若只有两个结点的度数是奇数，其余结点度数为偶数，则该图为半欧拉图。 判断一个图是否欧拉图 若是欧拉图，则输出"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”。

设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 （ ） 个5 度结点。

设G中有n个5度结点，则有9-n个6度结点。因为每个结点的度数只能是5或6，所以G中总共有 $5n+6(9-n)=54-n$ 条边。根据握手定理，G中边数应该是所有结点的度数之和的一半，即 $\frac{1}{2}\sum_{v\in G} d(v)$。由于每个结点的度数都不是5就是6，所以 $\sum_{v\in G} d(v)$ 必定是偶数。因此，$5n+6(9-n)=54-n$ 必须是偶数，解得 $n\geq 3$。因此，G中至少有3个5度结点。