证明1: 最小生成树必然存在

根据well ordering principle，集合必然存在最小值,所以最小生成子树必然存在.

证明2: 最小生成树可能有多个.

显然,边权为1的图的每个生成树都是最小生成树

证明3: 最小生成树必然包含图G上最短的那条边

反证法. MST添加最小边e后一定有环(n条边,n个点,),去除环上的一条边$e'$后, 形成了一条更小的MST树,矛盾.

证明: 最小生成树必然包含图 G 上最短的那条边

证明步骤：

1. 设定最短边： 设图 $G$ 中存在一条最短边 $e$，其权重为 $w(e)$，且 $e$ 连接两个顶点 $u$ 和 $v$。

2. 假设 $e$ 不在最小生成树中： 假设 $T$ 是 $G$ 的一棵最小生成树，但不包含边 $e$。

3. 构造图： 在 $T$ 中，去掉任意一条边 $e'$ 以保持树的特性（去掉一条边会产生两个连通分量）。由于 $T$ 是一棵树，去掉边 $e'$ 会将树分成两个连通分量，设为 $C_1$ 和 $C_2$。

4. 添加边 $e$： 由于 $e$ 连接 $C_1$ 和 $C_2$，我们可以将边 $e$ 加入 $T$。加入 $e$ 后，图中会形成一个环。

5. 考虑环中的边： 该环中包含了边 $e$ 和之前的边 $e'$。现在我们考虑这个环中的边权：

   • 因为 $e$ 是最短边，且其权重 $w(e)$ 小于或等于环中其他任何边的权重。

6. 替换边： 我们可以用边 $e$ 替换边 $e'$，得到一棵新的生成树 $T' = T - e' + e$。因为 $e$ 是最短边，所以 $w(e) \leqslant w(e')$，于是 $T'$ 的总权重不大于 $T$。

7. 得出矛盾： 由于 $T$ 已经是一棵最小生成树，总权重不可能再变小，所以 $T'$ 也是一棵最小生成树；但 $T'$ 包含了边 $e$，这与“$e$ 不在最小生成树中”的假设矛盾。

所以假设不成立，图 $G$ 上最短的那条边一定出现在最小生成树里。

证明3(核心):

    4
    |     
    |     
    1 --- 2
    |     
    |     
    3

若森林A是某个最小生成树的子图,去除A的条一边后e1,添加一边e2,且$e_2 \leqslant e_1$,那么形成的森林一定也是某个最小生成树的子图.

Kruskal算法的步骤如下

1. 首先，将图中所有边按权重从小到大排序。
2. 然后，从权重最小的边开始，将它和它所连接的两个顶点加入到一个连通子集中。
3. 重复步骤2，直到所有顶点都属于一个连通子集。
4. 最后，将所有边加入到最小生成树中，使得它是连通的。

证明3: Kruskal算法的正确性

使用数学归纳法

P(0) 是空集,必然是某个$MST$的子图.

假设P(i)成立,证明P(i+1) 成立

已知,P(i)是成立的,P(i)这森林一定是对应某个MST的子图.

现在添加一条边e, 最小的e,

证明过程与原来的证明3类似.