中国科学院大学 2023年强基第2题

（1） 设图 $G$ 是有 $n$ 个顶点，$m$ 个边，$r$ 个面的连通平面图，则有 $n-m+r=2$ 证：对边数 $m$ 用归纳法 当 $m=1$ ，图 $G$ 有两种结构 （1）$n=2, ~ m=1, ~ r=1$ 时，即《，$n-m+r=2$ 成立 （2）设 $n=1, m=1, r=2$ 时，即 $n-m+r=2$ 成立 设 $m=k$ 时，欧拉公式成立 当 $m=k+1$ 时，具有 $k+1$ 个边的连通图可以看成由含有 $k$ 个边的连通图添加一条边后构成，可分为如下三种结构： ◯ ：相当于在 $G(n, m, r)$ 原来的两个顶点中添加一个边增加一个区域，此图为 $G(n, m+1, r+1), n-(m+1)+r+1=2$ 成立 ◯ ：相当于在 $G(n, m, r)$ 原来的一个顶点中添加一个边增加一个区域，此图为 $G(n, m+1, r+1), n-(m+1)+r+1=2$ 成立 ◯ ：相当于在 $G(n, m, r)$ 基础上添加一个边，增加一个顶点，没有增加区域，此图为 $G(n+1, m+1, r), n+1-(m+1)+r=2$ 成立 注：此证明略去了图论术语中的树和圈，通过画出示意图，方便没有图论基础的学生看懂。 （2） 证：设多面体有 $f_{3}$ 个三角形，$f_{4}$ 个四边形，$\cdots$ ，即有 $f_{k}$ 个 $K$ 边形， 由于凸 $K$ 边形的内角和为 $(K-2) \pi$ ，则有 $\sum \alpha_{i}=\sum(K-2) \pi \cdot f_{k}=\pi \sum K f_{k}-2 \pi \sum f_{k}$ 又因为 $f=\sum f_{k}$（多面体的总面数） 所以 $\sum \alpha_{i}=\pi \sum K f_{k}-2 \pi f$ ， 易知 $\sum K f_{k}$ 是各个面的边数之和