度序列

度序列（degree sequence）是把图中每个顶点的度数排成的序列。对无向简单图，顶点的度是与它相邻的顶点数；通常将度数按非递增顺序排列，以便比较不同标号的图。一个非负整数序列若能由某个无向简单图实现，称为可图序列，实现它的图称为一个实现。

例如，取顶点 $a,b,c,d,e$ 及边 $ab,ac,bc,cd,de$。顶点 $c$ 接着 $a,b,d$，所以度为三；其余度数为 $\mathrm{deg}(a)=2,\mathrm{deg}(b)=2,\mathrm{deg}(d)=2,\mathrm{deg}(e)=1$。按顶点次序写为 $(2,2,3,2,1)$，排序后为 $(3,2,2,2,1)$。排序会丢去顶点名字，却保留各度数出现多少次。

每个数只数与该顶点接触的边；c的度为三，e的度为一。

握手引理与最初的筛选

设无向简单图有 $n$ 个顶点、$m$ 条边，度序列为 $d_1,\dots ,d_n$。每个顶点至多邻接另外 $n-1$ 个顶点，因此 $0\le d_i\le n-1$。更强的共同约束来自握手引理： $$\sum _{i=1}^n{d}_i=2m.$$

证明。 考察全部“顶点—与它关联的边”配对。按顶点分组，顶点 $i$ 提供 $d_i$ 个配对，总数为左端。按边分组，每条无向边有两个不同端点，提供两个配对，总数为右端。两种计数针对同一有限集合，所以相等。若允许自环并约定每个自环对度贡献二，结论仍成立；这里的上界 $n-1$ 却依赖简单图条件。

主例的和为 $3+2+2+2+1=10$，因此边数为五，与边表一致。又因为偶数度之和是偶数，奇数度之和的奇偶性等于奇数度顶点的数量，而总和为偶数，所以奇数度顶点的数量必为偶数。主例只有度为三的 $c$ 和度为一的 $e$，数量是二。

这些条件能排除许多序列。例如 $(2,2,1)$ 的和为五，不可图；$(4,1,1,0)$ 中最大度超过三，也不可图。但通过两道检查仍不保证可图，原因是各顶点的度必须由同一批边同时实现。

顶部度数的容量约束

对已排序序列 $n-1\ge d_1\ge \cdots \ge d_n\ge 0$，考察前 $k$ 个顶点组成的集合 $S$。它们度数的总和来自内部边和跨出 $S$ 的边： $$\sum _{i=1}^k{d}_i=2e(S)+e(S,V\setminus S).$$ 内部最多有 $(\genfrac{}{}{0ex}{}{k}{2})$ 条边，贡献至多 $k(k-1)$。外部顶点 $j$ 一方面总共只有 $d_j$ 条边，另一方面最多连接 $S$ 中的 $k$ 个不同顶点，所以对跨边贡献至多 $min(k,d_j)$。逐个外部顶点相加，便证明了必要条件 $$\sum _{i=1}^k{d}_i\le k(k-1)+\sum _{j=k+1}^{n}min(k,d_j),1\le k\le n.$$ 这段计数是条件的直接证明，不依赖任何图构造方法。

Erdős—Gallai定理进一步断言：上述整数序列可图，当且仅当总和为偶数，并且对所有 $k=1,\dots ,n$ 都满足这些不等式。这里的充分性是额外的定理；前面的计数只证明必要性。

现在检查 $(3,3,1,1)$。各项都在零到三之间，总和为八，也是偶数。但取 $k=2$ 得 $$3+3=6>2(2-1)+min(2,1)+min(2,1)=4.$$ 因此它不可图。还可直接解释：前两个顶点度均为三，必须各自与另外三个顶点相连；后两个顶点于是至少各接到这两个高度顶点，度不可能只有一。这是握手引理没有捕捉到的局部容量冲突。

主例的实现与有解答的变式

对于 $(3,2,2,2,1)$，不必仅依靠判据，也可直接给出实现。让度为三的顶点 $c$ 与 $a,b,d$ 相连，这三条边使这些邻居剩余需求分别为一、一、一，顶点 $e$ 的需求仍为一。再加 $ab$ 和 $de$，四个剩余需求同时归零。得到的正是开头的五条边，既没有自环，也没有重复边。

这种写法逐步核对“尚欠几条关联边”，比只画一张看起来合理的图更便于查错。但任意挑邻居可能把本来可图的序列带入死局；系统地每次连接当前最大度的若干顶点，需要 Havel—Hakimi 定理作为依据，不能由一次成功构造推出任意选择均可。

变式。 将序列改为 $(3,2,2,1,0)$，保持五个顶点。一个度零顶点必须孤立，因此在其余四个顶点中实现 $(3,2,2,1)$。令 $a$ 与 $b,c,d$ 相连，再加 $bc$，得到度数 $3,2,2,1$；加回孤立点即可。边数为 $(3+2+2+1)/2=4$。这个变式检验了零度顶点应占据一个顶点位置，却不消耗任何边。

同一度序列保留和遗漏的信息

度序列立即给出顶点数、边数、最大度和最小度；却一般不决定连通性、三角形数或图的同构类型。例如六顶点环 $C_6$ 与两个互不相连的三角形 $C_3\cup C_3$，每个顶点的度都为二，度序列同为 $(2,2,2,2,2,2)$。前者连通且没有三角形，后者有两个连通分量和两个三角形。两图均有六条边，符合握手引理。

如果 $G$ 为 $n$ 顶点简单图，补图中顶点 $v$ 的度为 $n-1-{\mathrm{deg}}_G(v)$，因为原来的邻居和非邻居在另外 $n-1$ 个位置中互补。排序后，补图的度序列是 $$(n-1-d_n,n-1-d_{n-1},\dots ,n-1-d_1).$$ 主例由此得到 $(3,2,2,2,1)$，与原序列恰巧相同；这只能说明两图度序列相同，不能单凭此式断言原图与补图同构。