【图论笔记】图论基础（5）：顶点的度

---

目录

• 1. 最大度、最小度和平均度
• 2. 正则图
• 返回【图论笔记】

---

1. 最大度、最小度和平均度

设$G$是一个图．$G$中所有顶点的度中的最大值叫做$G$的最大度，记作$\Delta(G)$或$\Delta$；所有顶点的度中的最小值叫做$G$的最小度，记作$\delta(G)$或$\delta$；所有顶点的度的平均数叫做$G$的平均度，记作$d(G)$．由握手定理可知：

性质1. $d(G)=\frac{2e(G)}{v(G)}.$

下面著名定理来自传奇的 Erdös，它在顶点染色中有着非常重要的应用．

定理2. 设$G$是一个图，$k$是一个正整数．如果$d(G)\ge2k$，那么$G$有一个导出子图$F$使得$\delta(F)\ge k+1$，并且这个界是紧的．

证明. 设$F$是$G$的平均度最大的导出子图中顶点数最少的一个．所以$d(F)\ge d(G).$下证$\delta(F)\ge k+1$．当$v(F)=1$时，$\delta(F)=d(F)\ge d(G)\ge 2k\ge k+1$，结论成立．不妨设$v(F)\ge2$．假设存在$v\in V(F)$使得$d(v)\le k$．令$F'=F\setminus v$．那么$d(F')=\frac{2e(F')}{v(F')}=\frac{2[e(F)-d(v)]}{v(F)-1}\ge\frac{2e(F)-2k}{v(F)-1}\ge\frac{2e(F)-d(G)}{v(F)-1}\ge\frac{2e(F)-d(F)}{v(F)-1}=d(F),$但是$v(F')<v(F)$，这与$F$的取法矛盾．$\Box$

---

2. 正则图

如果一个图的每个顶点的度都是常数$k$，那么这个图叫做==$k$-正则图==，简称正则图．

• 1-正则图是若干个$K_2$的不交并（这种图也叫匹配）．
• 2-正则图是若干个圈的并
• 3-正则图很复杂，在图论中有特殊地位，但目前没有很好的刻画．
• 完全图是特殊的正则图．

---

• 返回【图论笔记】