求加权连通简单图 $(G,\pmb{w})$ 中最小树的 Kruskal 算法如下：
- 选取 $e_1\in E(G)$ 使 $\pmb{w}(e_1)$ 尽可能小
- 若 $e_1,\dots,e_i$ 选定，则取 $e_{i+1} \in E(G) \backslash {e_1,\dots,e_i}$ 使 $G[{e_1,\dots,e_i,e_{i+1}}]$ 不含圈且 $\pmb{w}(e_{i+1})$ 尽可能小
- 若 $i<n-1$，则转 2；若 $i=n-1$，则停止
(a) 证明：由 Kruskal 算法构作 $G$ 的子图必是 $G$ 的最小树
(b) 利用 Kruskal 算法求出下图中最小树
结果是支撑树，记 $T_k=G[{e_1,\dots,e_k}]$，考虑最大的 $k$ 使得存在 G 中的最小树 $T_{\min}$ 满足 $T_k\subseteq T_{\min}$
若 $k=n-1$ 则证毕，否则 $e_{k+1} \notin T_{\min}$，故 $T_{\min}+e_{k+1}$ 含圈 $C$，易知 $\exist e^\prime \in [V_k,\overline{V_k}] \cap E(C)$，且 $e^\prime \neq e_{k+1}$。令 $T^\prime=T_{\min}+e_{k+1}-e^\prime$，其为支撑林，且 $T_{k+1} \subseteq T^\prime$。由算法知 $\pmb{w}(e_{k+1})\le \pmb{w}(e^\prime)$，故 $\pmb{w}(T^\prime)=\pmb{w}(T_{min})+\pmb{w}(e_{k+1})-\pmb{w}(e^\prime)\le \pmb{w}(T_{min})$，则 $T^\prime$ 也是最小树，这与 $k$ 的最大性矛盾。因此 $k=n-1$，证毕。
左 18，右 10
某公司在六个城市 $x_1,x_2,\dots,x_6$ 中都设有分公司，从 $x_i$ 到 $x_j$ 的直接航程票价由下列矩阵的第 $(i,j)$ 元素给出（$\infty$ 表示无直达航线）。试为该公司制作一张任意两城市之间的最廉价路线表。
$$
\left( \begin{array} { c c c c c c } { 0 } & { 50 } & { \infty } & { 40 } & { 25 } & { 10 } \ { 50 } & { 0 } & { 15 } & { 20 } & { \infty } & { 25 } \ { \infty } & { 15 } & { 0 } & { 10 } & { 20 } & { \infty } \ { 40 } & { 20 } & { 10 } & { 0 } & { 10 } & { 25 } \ { 25 } & { \infty } & { 20 } & { 10 } & { 0 } & { 55 } \ { 10 } & { 25 } & { \infty } & { 25 } & { 55 } & { 0 } \end{array} \right)
$$
设 $G$ 是 $n(\ge 4)$ 阶图，$\Delta=\Delta(G)$，$n_i$ 表示 $G$ 中 $i$ 度点数目。证明：
(a) 若 $G$ 是三角剖分图，则 $3n_3+2n_4+n_5=n_7+2n_8+\dots+(\Delta-6)n_\Delta + 12$
(b) 若 $G$ 是树，则 $n_1=n_3+2n_4+3n_5+\dots+(\Delta-2)n_\Delta+2$
对于三角剖分图，$e(G)=3n-6$，且 $\delta(G)\ge3$，则
$$
\sum_{i=3}^\Delta i n_i=\sum_{v\in V(G)} d_G(v) = 2e(G) = 6n-12=\sum_{i=3}^\Delta 6n_i-12
$$
移项即可
对于树，$e(G)=n-1$，且 $\delta(G)=1$，则
$$
\sum_{i=1}^\Delta i n_i=\sum_{v\in V(G)} d_G(v) = 2e(G) = 2n-2=\sum_{i=1}^\Delta 2n_i-2
$$
移项即可
证明：
(a) 若 $G$ 是围长 $g\ge 3$ 的 $n$ 阶连通平面图，则 $e(G)\le g(n-2)/(g-2)$
(b) Petersen 图是非平面图
- 顶点数 $v=10$
- 边数 $e=15$
- 分支数 $ω=1$
- 各顶点的度为 $d(v)=3$，因而它是三正则图（顶点的度只与之相连的边的数目）
- 围长 $g=5$（一个图的围长是指它所包含的最短圈的周长，由于通过枚举可以发现Petersen图中无三圈与四圈，其围长为5）
- 直径 $d=2$（一个图两点间的距离指其间最短路的长，而它的直径则指全图中最大的距离）
欧拉公式 $\phi=e-n+2$，又 $\forall f \in F(G)$，有 $d_G(f)\ge g$，则
$$
g(e-n+2)=g\phi\le \sum_{f\in F(G)}d_G(f)=2e
$$
移项即可
边数 $e=15$，围长 $g=5$，顶点数 $n=10$，又
$$
15=e\le g(n-2)/(g-2)=5(10-2)/(5-2)=40/3
$$
不成立，则 Petersen 图是非平面图
设 $G$ 是简单平面图，且 $\Delta(G)=n-1$，证明：若 $n\ge 5$，则 $G$ 中存在不相邻两顶点使其顶点度都 $\le 3$
考虑 G 可导出一个极大平面图 $G^\prime$，即三角剖分
顶点为 $x_1,\dots,x_n$，不妨设 $d(x_1) = \Delta$，不妨设 $x_2,\dots,x_n$ 对于 $x_1$ 是顺时针序的
存在平面表示 $\widetilde{G^\prime}$ 使得 $x_1$ 在外部面边界上，则 $x_2$ 和 $x_n$ 在外部面边界上，并且 $\widetilde{G^\prime}[{x_2,\dots,x_n}]$ 内部面是三角形，可归纳法证其中有 2 个不相邻的 2 度点，其在 $G^\prime$ 中即为不相邻的 3 度点。这两点在 $G$ 中也是不相邻且度数 $\le 3$。
