握手引理

一条边具有两个端点位置，即使自环的两个端点落在同一个顶点，它们仍是两个位置。把每条边的这两个位置分别记成两张关联记录，全图共有 $2|E|$ 张记录。改为按记录落在哪个顶点分组，顶点 $v$ 恰收到 $\mathrm{deg}(v)$ 张，于是两边在数同一批东西。

对无自环图，也可直接数关联对 $(v,e)$；含自环时单用这样的有序对集合会把同一自环的两个端点合并，所以要保留端点位置或计重。这是度数约定在证明中不可省略的原因。

令 $O$ 为奇度顶点集合。偶度顶点的度数和为偶数，故

奇度顶点因此成偶数个；定理不要求事先找出它们如何两两配对。

三角形的度数为 $(2,2,2)$，其和 $6$ 是三条边的两倍。在顶点 $a$ 加一个自环后，度数变为 $(4,2,2)$，边数变为四，等式仍为 $8=2\cdot 4$。若把自环只算一次，就会得到错误的总和七。

偶数度数和只是简单图可实现性的必要条件。例如 $(3,3,1,1)$ 的和为八，每项也不超过 $n-1=3$，却仍不可实现：两个度数为三的顶点都必须连接其余三个顶点，迫使另外两点的度数至少为二。更完整的条件由图度序列与可实现性理路图度序列与可实现性Graphical degree sequence · Graphic sequence用 Havel–Hakimi 约化和 Erdős–Gallai 不等式刻画有限简单无向图的度序列。给出。

有向图需分别计入度与出度，每条有向边各贡献一次，故 $\sum _v{\mathrm{deg}}^{+}(v)=\sum _v{\mathrm{deg}}^{-}(v)=|E|$。无限图不能照搬有限整数的奇偶推论：单向无限链 $v_0{v}_1{v}_2\cdots$ 只有一个奇度顶点 $v_0$，其他顶点度数均为二。

若 $|V|=n>0$、$|E|=m$，平均度为 $2m/n$。若所有顶点度数都大于平均值，把这些严格不等式相加就会得到度数和大于 $2m$，矛盾；全部小于平均值也同样不可能。因此至少有一顶点度数不超过平均值，也至少有一顶点不小于它。特别地，$d$-正则图满足 $nd=2m$；若 $d$ 为奇数，顶点数必须为偶数，但这只是必要条件，还须满足简单图的 $0\le d\le n-1$ 等约束。

Euler 道判定理路Euler 道判定Euler trail criterion · Eulerian trail theorem有限无向图存在遍历每条边恰一次的道路，当且仅当非孤立部分连通且奇度顶点数为零或二。利用度数奇偶限制开放迹的端点；平面图 Euler 公式理路平面图欧拉公式Euler's formula for planar graphs连通平面图的顶点数、边数与面数满足 V−E+F=2。结合面侧关联的类似双计数，可导出平面边数上界。在完全图理路完全图Complete graph每一对不同顶点都恰有一条边相连的有限简单无向图。中每点度为 $n-1$，握手式立即给出 $|E|=n(n-1)/2$。

把关联记录换成另一种对象 ​

握手证明可迁移成一个检查步骤：先明确两个有限集 $X,Y$ 及记录集合 $\mathcal{R}\subseteq X\times Y$，再分别按两个坐标求和，得到

例如对 $n\ge 1$、$1\le k\le n$，令 $\mathcal{R}=\{(a,S):S\subseteq [n],|S|=k,a\in S\}$。先选 $S$ 再标记一个元素得到 $k(\genfrac{}{}{0ex}{}{n}{k})$；先选 $a$ 再补其余元素得到 $n(\genfrac{}{}{0ex}{}{n-1}{k-1})$。两者都是同一批“子集加标记”，不必展开阶乘才能解释等式。

再取 $k\ge 1$，把 $S$ 换成棋盘上的 $k$ 车放置，标记其中一辆车。按放置计为 $k{r}_k(B)$；按被标记的格子 $s$ 计数，先删去它的行列，剩下 $k-1$ 辆车，所以

零车时没有可标记的车，独立得到 $0=0$，不需要定义 $r_{-1}$。这个公式来自车放置理路车多项式与禁位排列Rook polynomial · 禁位棋盘计数把兼容的禁位交集编码为非攻击车，证明删占递推、独立分块乘积和禁位排列的容斥公式。同样的关联记录，可复算递推结果。标记必须能从结果中识别；若忘掉标记或把有重复的记录当作集合去重，就会像把自环两个端点合并一样破坏计数。