小蓝书 17.2

喜欢水文章。

度数

与一个顶点 $v$ 关联的边的条数称作该顶点的 度 (degree)，记作 $d(v)$。特别地，对于边 $(v, v)$，则每条这样的边要对 $d(v)$ 产生 $2$ 的贡献。

对于无向简单图，有 $d(v) = \left| N(v) \right|$。

握手定理（又称图论基本定理）：对于任何无向图 $G = (V, E)$，有 $\sum_{v \in V} d(v) = 2 \left| E \right|$。

推论：在任意图中，度数为奇数的点必然有偶数个。

若 $d(v) = 0$，则称 $v$ 为 孤立点 (isolated vertex)。

若 $d(v) = 1$，则称 $v$ 为 叶节点 (leaf vertex)/悬挂点 (pendant vertex)。

若 $2 \mid d(v)$，则称 $v$ 为 偶点 (even vertex)。

若 $2 \nmid d(v)$，则称 $v$ 为 奇点 (odd vertex)。任意图中奇点的个数是偶数。

若 $d(v) = \left| V \right| - 1$，则称 $v$ 为 支配点 (universal vertex)。

对一张图，所有节点的度数的最小值称为 $G$ 的 最小度 (minimum degree)，记作 $\delta (G)$；最大值称为 最大度 (maximum degree)，记作 $\Delta (G)$。即：$\delta (G) = \min_{v \in G} d(v)$，$\Delta (G) = \max_{v \in G} d(v)$。

在有向图 $G = (V, E)$ 中，以一个顶点 $v$ 为起点的边的条数称为该顶点的 出度 (out-degree)，记作 $d^+(v)$。以一个顶点 $v$ 为终点的边的条数称为该节点的 入度 (in-degree)，记作 $d^-(v)$。显然 $d^+(v)+d^-(v)=d(v)$。

对于任何有向图 $G = (V, E)$，有：

$$\sum_{v \in V} d^+(v) = \sum_{v \in V} d^-(v) = \left| E \right|$$

若对一张无向图 $G = (V, E)$，每个顶点的度数都是一个固定的常数 $k$，则称 $G$ 为 $k$ - 正则图 ($k$-regular graph)。

---

上面只是概念，我们来证明几个东西吧。

1. 握手定理：对于任何无向图 $G = (V, E)$，有 $\sum_{v \in V} d(v) = 2 \left| E \right|$。

   证明：图 $G$ 中的每条边都贡献两次，总和就是 $2 |E|$ 。$\square$

2. 任意图中奇点的个数是偶数。

   证明：记 $a = \sum_{v \in V\setminus S} d(v),~b = \sum_{v \in S} d(v)$ ，其中 $S$ 为奇点构成的子集

   显然 $a+b = 2|E|$ ，则 $a = 2|E| - b$ 。因为 $2|E|$ 为偶数，所以 $a,b$ 一定同奇偶。$\square$

---

题解之后写。