由于看的课的中文是机翻，下面对 $walk,path$ 等词语在可能混淆的情形下使用英文。
由于画图的麻烦性，并没有画图，建议自行作画。
途径(walk) 是由由边链接的顶点的序列，允许顶点和边的重复。经过的边的数量 $k$ 称为路径长度。
路径(path) 不允许边或顶点的重复的 $walk$ 。
Lemma 1 path的存在性
如果存在从节点 $u$到$v$的$walk$那么就存在$u$到$v$的$path$ 。
[!证明]
存在 $walk$从$u$到$v$，根据良序定理，存在一个长度最小的$walk$。下面证明这就是一条$path$ 。
如果长度等于 $0,1$ ，显然成立。
如果长度 $k \geq 2$ ：
使用反证法，如果不是 $path$，那么就有重复的顶点，设$v_i=v_j$，则路径$u=v_0->…->v_i=v_j->…->v=v_k$是一条更短的路(砍掉了$v_i->v_j$的部分)。这就出现了矛盾。所以$Lemma$ 成立。
连通性 ：如果有一条从 $u$到$v$的$walk$ ，那么他们连通。如果一个图的每个顶点都连通，那么称该图连通，或称为连通图。
闭途径(closed walk) 是指一个起点和终点相同的 $walk$ 。
环(cycle) 是指不重复经过顶点的 $closed\ \ walk$ 。
树 ：连通无环图。
叶 ：树中 $degree$为$1$ 的节点。
Lemma 2 树的连通子图还是树
[!证明]
反证法。子图已经连通，假设子图有环，则原图有环，则不是树，矛盾，故子图无环(显然如此)。
Lemma 3 树的边数
节点为 $n$的树有$n-1$ 条边。
为证明此，先说明叶子的存在性。
证明：在任何 $n \ge 2$ 的树中，至少存在两个叶子节点
证明步骤：
取最长路径：
在树 $T$中，由于节点数有限且无环，一定存在一条最长路径（Path，点不重复），我们将其记为$P = (v_0, v_1, v_2, \dots, v_k)$。
考察端点 $v_0$：
考虑与起点 $v_0$相连的节点。除了路径上的邻居$v_1$ 之外，$v_0$ 还能有其他的邻居吗？
情况 A： 如果 $v_0$与路径之外的某个点$u$相连，那么我们可以把路径延长为$(u, v_0, v_1, \dots, v_k)$。这与 $P$ 是“最长路径”的假设矛盾。
情况 B： 如果 $v_0$与路径上已有的某个点（比如$v_i$，其中 $i > 1$）相连，由于 $v_0$和$v_i$ 之间已经有一条路径，这条新边会形成一个环。这与树“无环”的定义矛盾。
得出结论：
因此，$v_0$只能与$v_1$ 这一个点相连。也就是说，$v_0$的度数$\deg(v_0) = 1$。
同理推导：
同样的逻辑也适用于路径的另一个端点 $v_k$，它的度数也必然为 1。
结果： 路径 $P$的两个端点$v_0$和$v_k$ 都是叶子节点。证毕。
[!证明Lemma 3]
归纳法。
$n=1,2$ 时显然成立。
若 $n=k$时成立，$n=k+1$时： 删掉一个叶子，那么创造了一个连通子图，根据$Lemma$ $2$这就是$n=k$的树，那么满足有$k-1$条边，加上这个叶子，那么也只会加上一条边，那么此时就恰好有$k$ 条边。
生成树(Spanning tree,ST) ：一个连通图的子图，该子图是一个包含所有节点的树。
生成树是包含所有顶点最小连通子图的解。
Theorem 每个连通图都有生成树
[!证明]
假设有一个连通图 $G$没有生成树。让$T$作为满足是$G$的一个连通子图，拥有$G$ 的全部顶点的子图中有最小边数的子图。
那么根据假设，$T$有环，那么删去环上的一条边，边数变短了，但仍然是连通图，这与$T$ 边数最小矛盾，所以原命题成立。仍然连通的说明：考虑任意两个顶点 $x,y$，若连接他们的$walk$不包含删去的边$e$，那么当然不会破坏他们的连通性；反之，由环的定义，除了边$e$之外，$e$的顶点$u$和$v$之间一定存在另一条$path$ $P_{uv}$，那么$x,y$之间就存在路线$(x, \dots, u) + P_{uv} + (v, \dots, y)$ ，可见仍然是连通的。
最小生成树(MST) ：对于有权重的连通图，权值和最小的生成树。
Kruskal 算法（加边法）
每次选择权重最小的边，只要不形成圈就行，直到变成生成树。就变成了最小生成树。
[!Lemma]
$\forall G$，让$S$为包含了按照算法选择的其前$m$条边的集合。则存在最小生成树$T=(V,E)$，使得$S \in E$。证明：
使用归纳法。归纳假设 $P$ 即命题。$m=0$ 时，$S$ 是空集，显然成立。
设 $P(m)$成立，设$e$是第$m+1$步添加的边，让$S$表示已选择的前$m$条边，根据归纳假设，存在最小生成树$T^=(V,E^)$使得$S\in E^*$ 。
如果 $e\in E^$ ，那么显然成立，
反之，由于 $T^$是生成树，顶点已连通，再加边则会生成环，由$e$和连接其顶点$u,v$ 的路径组成。
由于 $S$按照算法选无环，这个环上必定有不属于$S$的边$e’$。由于算法先选$e$再选$e’$，可知$w(e) \leq w(e’)$ 。
构造新树 $T^{}$，为$T^*$删去$e’$加上$e$， 此时图依然连通无环，故$T^{}$也是生成树，且$w(T^{})=w(T^*)-w(T^{}) = w(T^) - w(e’) + w(e) \leq w(T^)$，因为$T^*$已经是最小生成树，只能取等，所以$T^{}$也是最小生成树。而显然这个新的$S’\in E^{}$ 。成立。综合以上，归纳得证原命题成立。
[!]
设连通图 $G$的顶点集合为$V$，有$n$个顶点，先证明能选出$n-1$ 条边。
根据 $Lemma$，存在最小生成树的边集$E$包含$S$，所以总可以选取$E$中有$S$中没有的边继续进行下去，而由于$E$是最小生成树的边集，显然会生成没有环的子图，直至有$n-1$ 条边。
.
选出之后，此时有 $S\in E$，同时他们元素个数相等，从而$S=E$ ，也就是说，算法生成了最小生成树。