无向图度数性质
一、基础概念：顶点度数定义
在无向图 $ G = (V, E) $ 中：
- 顶点 $ v \in V $ 的度数 $ \deg(v) $ 指关联于该顶点的边的数量
- 特殊情况：
- 环（$ (v, v) $）对 $ \deg(v) $ 贡献 2
- 孤立点度数为 0
- 非环边 $ (u, v) $ 对 $ \deg(u) $ 和 $ \deg(v) $ 各贡献 1
二、核心性质1：握手定理（Handshaking Lemma）
-
定理公式：
\( \sum_{v \in V} \deg(v) = 2|E| \)
（所有顶点度数之和 = 边数的2倍） -
证明依据：
- 非环边贡献：每条边为两个顶点各加1，合计2
- 环贡献：每条环为对应顶点加2，合计2
- 总贡献：$ 2 \times $ 边数
-
示例验证：
- 三角形（3顶点3边）：$ 2+2+2=6=2 \times 3 $
- 含1环的图（边 $ (v1,v1) $ 和 $ (v1,v2) \(）：\) 3+1=4=2 \times 2 $
三、核心性质2：握手定理推论
-
结论：度数为奇数的顶点个数必为偶数
-
推导逻辑：
- 度数总和为偶数（$ 2|E| $）
- 偶数度顶点之和为偶数
- 奇数度顶点之和必为偶数（偶数个奇数相加为偶数）
-
示例：
- 合法：$ [1,2,3,4,4] $（2个奇数度顶点）
- 非法：$ [1,2,3,4,5] $（3个奇数度顶点）
四、其他重要性质
-
简单无向图度数上限：
- 任意顶点度数 $ \leq n-1 \(（\) n $ 为顶点数）
- 原因：无环且无多重边，最多连接 $ n-1 $ 个其他顶点
-
正则图性质：
- $ k $-正则图（所有顶点度数为 $ k \(）满足：\) k \cdot n = 2|E| $
- 推论：若 $ k $ 为奇数，则 $ n $ 必为偶数
五、度数序列可图性
-
必要条件（非充分）：
- 序列总和为偶数
- 奇数个数为偶数
-
示例：
- 可图：$ [2,2,2] \(、\) [3,3,1,1] $
- 不可图：$ [3,3,3] $（总和为9，奇数）
-
充分性判断：可使用Havel-Hakimi算法