握手定理

一个图所有顶点度数之和为 $20$,它有多少条边?

$2|E| = 20 \Rightarrow |E| = 10$。

一个图有 $8$ 个顶点,每个顶点度都是 $6$,求边数。

度数和 $= 8\times6 = 48 = 2|E|$,故 $|E| = 24$。

一个图中可以恰好有 $3$ 个顶点的度为奇数。

奇数度的顶点个数必为偶数,不可能是 $3$。

$7$ 个人能否每人都恰好与其他 $3$ 个人握过手?

那样会有 $7$ 个奇数度顶点(奇数个),违反奇点定理,不可能。

握手定理 $\sum\deg(v) = 2|E|$ 成立是因为?

每条边连接两个顶点,被两端各记一次度,故度数和是边数的 $2$ 倍。