离散数学中的握手定理

握手定理也称为度数和定理或握手引理。握手定理指出，一个图中所有顶点的度数之和等于该图边数的两倍。握手定理的符号表示如下：

此处，

'd'用于表示顶点的度数。

'v'用于表示顶点。

'e'用于表示边。

握手定理

握手定理有一些必须得出的结论，现分述如下：

在任何图中：

• 所有顶点的度数之和必须是偶数。
• 如果所有顶点的度数都是奇数，那么这些顶点的度数之和必然是偶数。
• 如果存在一些度数为奇数的顶点，那么这些顶点的数量必然是偶数。

握手定理的例子

握手定理有各种各样的例子，其中一些例子分述如下：

示例 1：这里有一个图，其中每个顶点的度数都是 4，共有 24 条边。现在我们将找出该图中的顶点数。

解答：根据上述图，我们得到了以下详细信息：

每个顶点的度数 = 24

边数 = 24

现在我们假设顶点数为 n

根据握手定理，我们有以下关系：

所有顶点的度数之和 = 2 * 边数

现在我们将给定值代入上述握手公式：

n*4 = 2*24

n = 2*6

n = 12

因此，在图 G 中，顶点数为 12。

示例 2：这里有一个图，它有 21 条边，3 个度数为 4 的顶点，以及其他所有顶点度数都为 2。现在我们将找出该图中的总顶点数。

解答：根据上述图，我们得到了以下详细信息：

度数为 4 的顶点数 = 3

边数 = 21

所有其他顶点的度数都为 2

现在我们假设顶点数为 n

根据握手定理，我们有以下关系：

所有顶点的度数之和 = 2 * 边数

现在我们将给定值代入上述握手公式：

3*4 + (n-3) * 2 = 2*21

12+2n-6 = 42

2n = 42 - 6

2n = 36

n = 18

因此，在图 G 中，总顶点数为 18。

示例 3：这里有一个图，它有 35 条边，4 个度数为 5 的顶点，5 个度数为 4 的顶点，以及 4 个度数为 3 的顶点。现在我们将找出该图中度数为 2 的顶点的数量。

解答：根据上述图，我们得到了以下详细信息：

边数 = 35

度数为 5 的顶点数 = 4

度数为 4 的顶点数 = 5

度数为 3 的顶点数 = 4

现在我们假设度数为 2 的顶点数为 n

根据握手定理，我们有以下关系：

所有顶点的度数之和 = 2 * 边数

现在我们将给定值代入上述握手公式：

4*5 + 5*4 + 4*3 + n*2 = 2*35

20 + 20 + 12 + 2n = 70

52+2n = 70

2n = 70-52

2n = 18

n = 9

因此，在图 G 中，度数为 2 的顶点数为 9。

示例 4：这里有一个图，它有 24 条边，并且每个顶点的度数都是 k。现在我们将根据给出的选项找出可能的顶点数。

1. 15
2. 20
3. 8
4. 10

解答：根据上述图，我们得到了以下详细信息：

边数 = 24

每个顶点的度数 = k

现在我们假设顶点数为 n

根据握手定理，我们有以下关系：

所有顶点的度数之和 = 2 * 边数

现在我们将给定值代入上述握手公式：

N*k = 2*24

K = 48/n

任何顶点的度数必须是整数。

因此，我们在上述方程中只能使用能使 k 为整数的 n 值。

现在，我们将逐一将上述选项代入 n 来检查，如下所示：

• 当 n = 15 时，k = 3.2，不是整数。
• 当 n = 20 时，k = 2.4，不是整数。
• 当 n = 8 时，k = 6，是整数，是允许的。
• 当 n = 10 时，k = 4.8，不是整数。

因此，正确选项是 C。