我从初中毕业的暑假开始学习离散数学，参考的是胡新启的那本书。
本文主要摘要了当时的学习笔记，包含的是第六章图论和第七章树部分。

定义

平凡图：G = <1, 0> 是平凡图，也就是一个点。
无向图的最大度记为 $\Delta(G)$，最小度记为 $\delta(G)$。有向图的最大/小出度记为 $\Delta^+$ 和 $\delta^+$，最大/小入度记为 $\Delta^-$ 和 $\delta^-$。
简单图：不含环和平行边的图。
完全图 $K_n$：任意两个点都有边相连的简单图。

连通性

连通分支。

点断集/点割集，设 T 是 G = <V, E> 的真子图，如果 G - T 不连通，或者是平凡图，则 T 称为点断集或者点割集。如果 $ \{v\} $ 是点割集，那么 v 称为割点。定义点连通度如下。实际上就是最少要删 $\kappa(G)$ 个点才能不连通。
$$
\kappa(G) = min \{ |T| \, | \, T 为 G 的点断集 \}
$$
可得 n 阶完全图的点连通度为 n - 1。

定理：对于任意无向图 G，有
$$
\kappa(G) \le \lambda(G) \le \delta(G)
$$

先证明右边。
再证明左边。假设 G 有 n 个点，m 个边。讨论：

$\lambda(G)=0$，说明图本来就不连通或者平凡，显然 $\kappa(G)$ 是0。
$\lambda(G)=1$，删掉和割边关联的点即可。 $\kappa(G)$ 是1。
$\lambda(G) \ge m - 1$。因为 $\kappa(G)$ 最大只能取到 m - 1，也就是把 m - 1 条边对应的点不重复地去掉。所以 $ \kappa(G) \le \lambda(G) $。

下面证明最复杂的一种情况，即 $ 1 \lt \lambda(G) \lt m - 1 $，简写 $\lambda(G)$ 为 λ。不妨设这个大小为 λ 的边割集为 $ \{ e_1, e_2, …, e_{\lambda} \} $。
不妨考虑 $ G - \{ e_2, …, e_{\lambda} \} $，$ e_1 $ 是它的一条割边，令两个顶点分别为 u 和 v。我们可以在 $ e_2, …, e_{\lambda} $这 $\lambda -1$ 条边中，每条边上各去一个点且重复不计，但不能是 u 或者 v。我们最多能取 $\lambda -1$ 个，否则 $e_1$ 和其他的边都没有公共端点，它对这最小边割集没有贡献。
取出来的顶点集合记为 $ V_1 $。如果 $ G - V_1 $ 不连通，那么有 $ \kappa(G) \le \lambda - 1$。如果 $ G - V_1 $ 连通，比如下面的情况