图的度数

在无向图中，顶点的度数是与它相接的边端个数。普通边在两个端点各贡献 1；自环的两个端都落在同一顶点，因此给该顶点贡献 2。把自环只数一次会破坏下面的基本恒等式。

握手引理

把全图所有顶点的度数相加。每条边无论连接两个不同顶点，还是形成一个自环，都恰好贡献两个边端，所以 $$\sum _{v\in V}\mathrm{deg}(v)=2|E|.$$ 例如路径 $A-B-C$ 有两条边，三个顶点的度数依次为 $1,2,1$，总和 $1+2+1=4=2\cdot 2$。这不是对画得整齐的图才成立，而是逐条边计数的结果。

奇度顶点一定成对出现

等式右边为偶数，故左边所有奇度项的个数也必须为偶数；否则奇数个奇数相加，再加若干偶数，结果仍是奇数。这个结论能立即排除某些“画一条经过每条边一次的路线”的设想：欧拉路径若有两个不同端点，除了起终点之外，经过每个顶点的边要进出配对，故奇度顶点只能是这两个端点。

对于有向图，要分别数入度与出度，每条弧给一个顶点贡献一次出度、另一个顶点贡献一次入度。因此 $\sum _v{\mathrm{deg}}^{+}(v)=\sum _v{\mathrm{deg}}^{-}(v)=|E|$；不能把无向图的度数公式原封不动套用。

参考资料

• MIT，Mathematics for Computer Science，Graph Theory 章节。
• OpenStax《Contemporary Mathematics》第 12 章：图论。
• 继续阅读：图论、欧拉路径、树与生成树。