视频字幕
在图论中，顶点度数是一个基本概念，表示与某个顶点相连的边的数量。如图所示，顶点A连接2条边，所以度数为2。顶点C连接4条边，度数为4。握手定理告诉我们，所有顶点度数之和等于边数的两倍，这是因为每条边都被计算了两次。
握手定理的证明基于一个简单观察：每条边都连接两个顶点，因此每条边对度数总和的贡献恰好是2。如果图有E条边，那么所有顶点度数之和就是2E。这个定理有一个重要推论：图中奇度数顶点的个数必须是偶数，因为度数总和是偶数。
图序列理论研究哪些度数序列可以对应实际的图。Erdős-Gallai定理给出了判定条件：度数和必须为偶数，且满足特定不等式。Havel-Hakimi算法提供了构造性判定方法：取最大度数顶点，将其度数分配给其他顶点，递归判定剩余序列。
双射是组合数学中的重要工具，用于建立不同结构间的一一对应关系。在图论中，Prüfer序列提供了标号树与数字序列间的双射。通过这个双射，我们可以证明n个顶点的标号树共有n的n-2次方个，这是著名的Cayley公式。
极值图论研究在给定约束条件下图的最值性质。Turán问题是其中的经典问题：给定n个顶点，不包含r-团的图最多能有多少条边。Mantel定理是特殊情况，证明了无三角形的图最多有n²/4条边，完全二部图达到这个上界。